#P3821. 玄学

    ID: 3023 传统题 8000ms 512MiB 尝试: 144 已通过: 53 难度: 8 上传者: 标签>CF2500提高+/省选-普通线段树幺半群区间聚合双指针合并有序序列二分查找2015年国家集训队测试

玄学

题目描述

给定序列 a1⋯na_{1\cdots n} 与常数 mm,你需要维护并支持 qq 次以下操作:

  • 1 l r a b,添加一条 x←(ax+b) mod mx\gets (ax+b)\bmod m 且针对 al⋯ra_{l\cdots r} 的变换到计划中,即若执行这条计划,对于 l≤i≤rl\leq i\leq r,ai←(a×ai+b) mod ma_i\gets (a\times a_i+b)\bmod m;
  • 2 l r k,询问若执行计划中第 [l,r][l,r] 条变换,aka_k 的值会是多少。

注意询问独立,即不会对 aa 序列实际做出修改。

输入格式

第一行一个整数 typetype 表示这组数据的 特征值,它是一个 0∼310\sim 31 之间的整数,你需要将其转换为一个五位的二进制数,最低位为第一位,其意义如下:

如果第一位为 11,代表数据进行了加密,否则数据没有进行加密。对于已加密的数据,你需要把第一种操作中的 l,rl,r 以及第二种操作中的 l,r,kl,r,k 与上一次询问操作得到的答案 lastanslastans 进行异或操作来得到正确的操作信息。lastanslastans 初始值视为 00。

如果第二位为 11,代表修改操作会出现 (0x+b) mod m(0x+b)\bmod m(bb 不为 00)的形式,否则一定不会出现这样的修改。

如果第三位为 11,代表修改操作会出现 (ax+0) mod m(ax+0)\bmod m(aa 不为 00)的形式,否则一定不会出现这样的修改。

如果第四位为 11,代表修改操作会出现 (ax+b) mod m(ax+b)\bmod m(a,ba,b 均不为 00)的形式,否则一定不会出现这样的修改。

如果第五位为 11,则我们保证给出的 mm 是一个质数,否则不保证。

第二行两个整数 n,mn,m。

第三行 nn 个整数依次表示 a1⋯na_{1\cdots n}。

第四行一个整数 qq 表示操作次数。

接下来 qq 行,每行一个操作,格式见题目描述。

输出格式

对每个第 22 类操作,输出独占一行的一个整数,表示那次询问的结果。

24
3 5
1 2 3
5
1 1 2 3 2
1 2 3 4 3
2 1 1 3
1 1 3 1 4
2 1 3 2
3
4
7
3 5
1 2 3
5
1 1 2 0 3
1 2 3 4 0
2 1 1 3
1 2 0 2 0
2 2 0 1
3
4

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051\leq n\leq 10^5,1≤q≤6×1051\leq q\leq 6\times 10^5。

我们保证,同类型的测试点中加密与不加密的数据点各占 50%50\%,且修改操作数不超过 10510^5,所有数的都可以用 int 存下。

由于本题数据量较大,请自行使用读入优化;由于测试点较多以及时限较长,为了大家的正常做题,请尽量减少提交本题的次数。

来源

20152015 年国家集训队测试。