← 返回题目列表

AtCoder · awc0100_m

M. 秘密序列和分支注释

中文机器翻译题面 查看原题

分数: 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