分数: 500 分
问题陈述
Takahashi and Aoki are trying to deduce N 隐藏整数 A_1, A_2, \ldots, A_N.
每个 A_i 是介于 0 和 K - 1 inclusive, but the specific values are unknown to both of them.
的 分数 $$$v$$$ 的 一个区间 [L, R] 定义为以下值:
(A_L + A_{L+1} + \cdots + A_R) \bmod K
The two manage their deduction records as "versions" of a note.
Each operation references an existing version and produces a new version as its result. This causes versions to branch out in a tree structure.
最初存在版本 0, which contains no accepted records.
Q 操作按顺序给出。
在 i第一次操作 (1 \leq i \leq Q),已经存在的版本 B (0 \leq B \leq i - 1)被引用,并且一个新的 版本 操作结果是创建 i 。
有两种类型的操作:
- 类型 0:
0 B L R X
青木声称,关于版本 B,即“区间的分数 [L, R] is X."
如果存在分配 (A_1, A_2, \ldots, A_N) 其中每个元素都是介于 0 和 K-1 包括同时满足版本中接受的所有记录 B 和 这个说法,那么 接受 此声明和输出 YES。在这种情况下,版本 i 由版本的接受记录组成 B 加上这个声明。
如果不存在这样的分配, 拒绝 此声明和输出 NO。在这种情况下,版本 i 与版本内容相同 B.
- 类型 1:
1 B L R
高桥询问区间分数是否 [L, R] 只能根据版本中接受的记录唯一确定 B.
如果,对于每个作业 (A_1, A_2, \ldots, A_N) (其中每个元素都是介于 0 和 K-1 包括在内)满足所有接受的版本记录 B,区间得分 [L, R] 是相同的值,然后输出该值。
如果不能唯一确定,则输出 UNKNOWN.
此操作不会添加任何新记录,且版本 i 与版本内容相同 B.
处理 Q 按顺序进行操作并输出每个操作的答案。
约束
- 1 \leq N \leq 2 \times 10^5
- 2 \leq K \leq 10^9
- 1 \leq Q \leq 10^5
- 在 i第一次操作 (1 \leq i \leq Q), 0 \leq B \leq i - 1
- 在每次操作中, 1 \leq L \leq R \leq N
- 输入类型 0 操作, 0 \leq X \leq K - 1
- 所有输入均为整数
输入
N K Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
第一行包含元素数量 N,模数 K,以及操作次数 Q,用空格分隔。
The following Q 行包含按时间顺序排列的操作。
A型 0 操作按以下格式给出:
0 B L R X
这表示一个操作,其中“间隔的分数 [L, R] is X“针对版本声明 B.
A型 1 操作按以下格式给出:
1 B L R
这代表一个操作,询问区间的分数是否 [L, R] 可以在版本中唯一确定 B.
输出
输出每个操作的答案 Q 行,按照给出的操作顺序。
- 对于类型 0 操作、输出
YES如果索赔被接受,或者NO如果被拒绝。 - 对于类型 1 操作,如果该值唯一确定,则将该值输出为介于 0 和 K - 1 包括在内;如果不唯一确定,则输出
UNKNOWN.
样本输入 1
4 5 8 1 0 1 2 0 0 1 2 3 1 2 1 2 0 2 3 4 4 1 4 1 4 0 2 1 4 1 1 6 3 4 1 4 3 4
示例输出 1
UNKNOWN YES 3 YES 2 YES 3 4
示例输入 2
3 7 7 0 0 1 3 2 0 1 1 1 4 0 2 2 3 5 0 2 2 3 6 1 4 2 3 0 4 1 3 3 0 0 1 3 3
示例输出 2
YES YES YES NO 5 NO YES
示例输入 3
8 10 18 0 0 1 4 6 0 1 5 8 3 1 2 1 8 0 2 3 6 7 1 4 1 2 0 4 1 2 9 1 6 3 6 0 6 1 8 0 1 8 1 8 0 4 1 2 1 1 10 5 6 0 10 5 6 3 1 12 7 8 0 0 2 7 4 1 14 1 8 0 14 1 1 2 0 16 8 8 5 1 17 1 8
示例输出 3
YES YES 9 YES UNKNOWN YES 7 NO 9 YES 2 NO 1 YES UNKNOWN YES YES 1
示例输入 4
20 1000000000 30 0 0 1 10 123456789 0 1 11 20 987654321 1 2 1 20 0 2 5 15 555555555 1 4 1 4 0 4 1 4 222222222 1 6 5 10 1 6 11 15 0 6 16 20 333333333 0 6 16 20 333333334 1 10 16 20 0 4 1 4 111111111 1 12 5 10 0 12 11 15 123456789 0 0 3 18 700000000 1 15 1 20 0 15 1 2 100000000 0 17 19 20 200000000 1 18 1 20 0 18 1 20 0 0 18 1 20 1 1 21 3 18 0 6 7 14 444444444 1 23 1 15 0 23 1 15 777777777 0 23 1 15 777777778 1 26 1 15 0 12 16 20 333333333 0 12 16 20 444444444 1 29 1 20
示例输出 4
YES YES 111111110 YES UNKNOWN YES 901234567 654320988 YES NO 333333333 YES 12345678 NO YES UNKNOWN YES YES 0 YES NO 700000000 YES 777777777 YES NO 777777777 NO YES 111111110
示例输入 5
1 2 8 1 0 1 1 0 0 1 1 0 1 2 1 1 0 2 1 1 1 1 4 1 1 0 0 1 1 1 1 6 1 1 0 6 1 1 1
示例输出 5
UNKNOWN YES 0 NO 0 YES 1 YES