QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 125 MB Total points: 100

# 7475. NOIP2016 人生巅峰

Statistics

题目描述

给一个长为 $n$ 的序列 $a_1,a_2,\ldots,a_n$,每个数在 $0$ 到 $v - 1$ 之间,有 $m$ 次操作。

操作 $1$:每次询问一个区间中是否可以选出两个下标的非空集合 $X,Y$,满足:

  1. $X$ 和 $Y$ 没有交集。
  2. 设集合 $X$ 中有一个元素是 $i$,则其对集合 $X$ 的贡献是 $a_i + 1$,要求集合 $X$ 的元素的总贡献和集合 $Y$ 的元素的总贡献相等。如果可以选出这两个集合,输出 Yuno 否则输出 Yuki

操作 $2$:修改一个区间 $l,r$ 之间的数,使得所有 $l\leq i\leq r$,$a_i = a_i^3 \bmod v$,即区间立方。

输入格式

第一行三个整数 $n , m , v$,意义如题所述。

之后一行 $n$ 个整数,表示序列 $a$。

之后 $m$ 行每行三个数 $opt , l , r$,表示操作类型是 $1$ 还是 $2$,操作的区间是 $[l , r]$。

输出格式

对每个询问输出一行一个字符串 Yuno 或者 Yuki 表示能否选出这两个集合。

样例 #1

样例输入 #1

20 20 152
3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58
2 1 17
2 6 12
1 1 12
2 3 5
2 11 11
2 7 19
2 6 15
1 5 12
1 1 9
1 10 19
2 3 19
2 6 20
2 1 13
2 1 15
2 1 9
1 1 1
2 1 7
2 7 19
2 6 19
2 3 6

样例输出 #1

Yuno
Yuno
Yuno
Yuno
Yuki

提示

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477

对于 $100\%$ 的数据,$1\leq n , m\leq 10^5$,$1\leq v\leq 1000$,数据没有梯度。