← 返回题目列表

Codeforces · 2123/G

G. 模块化排序

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

给定一个整数 $$$m$$$ ($$$2\leq m\leq 5\cdot 10^5$$$) 和一个由小于 $$$m$$$ 的非负整数组成的数组 $$$a$$$。

回答以下形式的询问:

  • $$$1$$$ $$$i$$$ $$$x$$$: 赋值 $$$a_i := x$$$
  • $$$2$$$ $$$k$$$:在一次操作中,您可以选择一个元素 $$$a_i$$$ 并分配 $$$a_i := (a_i + k) \pmod m$$$$$$^{\text{∗}}$$$ — 确定是否存在某种序列(可能为零)操作来生成 $$$a$$$非递减$$$^{\text{†}}$$$。

请注意,查询 $$$2$$$ 的实例是独立的;也就是说,没有发生任何实际操作。查询 $$$1$$$ 的实例是持久的。

$$$^{\text{*}}$$$$$a\pmod m$$$ 被定义为唯一整数 $$$b$$$,使得 $$$0\leq b \lt m$$$ 和 $$$a-b$$$ 是 $$$m$$$ 的整数倍。

$$$^{\text{†}}$$$大小为$$$n$$$的数组$$$a$$$被称为非递减当且仅当$$$a_i\leq a_{i+1}$$$对于所有$$$1\leq i \lt n$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数,$$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2\leq n \leq 10^5$$$, $$$2\leq m\leq 5\cdot10^5$$$, $$$1\leq q\leq 10^5$$$) - 的大小数组 $$$a$$$、整数 $$$m$$$ 和查询数量。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1,a_2,\dots,a_n$$$ ($$$0\leq a_i \lt m$$$)。

然后是 $$$q$$$ 行。每行具有以下形式之一:

  • $$$1$$$ $$$i$$$ $$$x$$$ ($$$1\leq i\leq n$$$, $$$0\leq x \lt m$$$)
  • $$$2$$$ $$$k$$$ ($$$1\leq k \lt m$$$)

保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^5$$$。

输出

对于查询 $$$2$$$ 的每个实例,在单行上输出“是“如果存在一些(可能为零)操作序列使$$$a$$$非递减,并且”NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

2
7 6 6
4 5 2 2 4 1 0
2 4
1 4 5
2 4
2 3
1 7 2
2 3
8 8 3
0 1 2 3 4 5 6 7
2 4
1 3 4
2 4

输出
复制

YES
NO
NO
YES
YES
NO

注意

在第一个示例中,数组最初为:

4522410

通过对 $$$a_1$$$ 应用操作两次,对 $$$a_2$$$ 应用操作两次,对 $$$a_5$$$ 应用操作一次,对 $$$a_6$$$ 应用操作两次,对 $$$a_7$$$ 应用操作一次,数组变为:

0122234
按非降序排列。

第二次查询后,数组变为:

4525410
并且可以证明,不可能使用 $$$a_i := (a_i+4)\pmod 6$$$ 形式的操作对其进行排序,也不可能使用 $$$a_i := (a_i+3)\pmod 6$$$ 形式的操作对其进行排序。