#P12090. [2024年联测]环

    ID: 11239 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-欧几里得算法随机哈希双哈希根号分治根号分块一维前缀和模逆元快速乘防溢出

[2024年联测]环

题目描述

给定一个整数环 AA 和一个允许长度的集合 SS。一次修改选择 k∈Sk\in S、环上的起点及一个实数 cc,把从该起点起沿环连续的 kk 个元素都加上 cc。每次可以独立选择 kk、起点和 cc。

若经过有限次修改能使 AA 中所有元素变成 00,则称 (A,S)(A,S) 是好的。

给定数组 a1,…,ana_1,\ldots,a_n,支持两类操作。

  • 1 x w 将 axa_x 修改为 ww。
  • 2 l r m 后另输入一行 mm 个整数 b1,…,bmb_1,\ldots,b_m。询问把 al,…,ara_l,\ldots,a_r 首尾相接得到的环,与长度集合 S={b1,…,bm}S=\{b_1,\ldots,b_m\} 是否组成一个好的 (A,S)(A,S)。输入中的长度可以重复。询问不改变数组 aa。

输入格式

第一行两个整数 n,qn,q。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来按顺序输入 qq 个操作。操作 1 占一行,操作 2 占两行。

输出格式

每次操作 2 输出一行。若对应的 (A,S)(A,S) 是好的,输出 YES,否则输出 NO。

样例 1

5 5
3 2 1 1 3
2 1 2 4
2 2 2 2
2 1 3 2
1 2
2 2 5 4
4 2 4 2
2 4 5 4
1 2 1 2
2 1 2 2
2 2
NO
YES
NO
YES
NO

样例 2

10 10
1 5 3 1 3 2 3 2 5 2
2 2 6 2
2 4
2 7 9 1
2
1 5 0
1 7 3
2 4 9 4
2 6 2 2
1 2 6
2 1 4 3
4 4 4
1 4 4
1 4 7
1 4 10
YES
YES
NO
NO

原题另在下发文件中提供样例 3–8,样例 4–8 分别满足子任务 1–5 的限制。

数据范围

5≤n,q≤2×1055\le n,q\le2\times10^5,∣ai∣,∣w∣≤1012|a_i|,|w|\le10^{12},1≤m,x≤n1\le m,x\le n,1≤l≤r≤n1\le l\le r\le n,1≤bi≤r−l+11\le b_i\le r-l+1,所有询问的 mm 之和不超过 2×1062\times10^6。

原子任务 分值 附加限制
1 10 n,q≤5000n,q\le5000,bi≤2b_i\le2
2 30 n,q≤5000n,q\le5000
3 10 bi≤2b_i\le2
4 bi≤20b_i\le20
5 40 无

原 PDF 题面