卡常线段树模板

提交数: 67, 通过率: 2.99%, 平均分: 6.87

题目描述:

现在有一个长度固定为\( 2097150 = 2^{21} - 2 \)的序列\( a \)。
你要对这个序列进行以下操作:
1 i j 修改\( a_i \)为j
2 i j 查询\( a_i \)到\( a_j \)的最大值。

序列\( a \)的初始值全为0。

询问的生成方式如下:

int gen(long long&seed,int range){
return (seed=(seed*19260817ll+73939133ll)%998244353ll)%range+1;
}

先用gen(seed,2)生成询问类型,然后用gen(seed,2097150)生成i,用gen(seed,2097150)生成j,共生成M次
若询问类型为2,若i>j交换i和j。

输入格式:

输入2个整数M,Seed

输出格式:

输出1个整数,所有的2询问答案的异或和。

样例输入:

样例1
8 888888
样例2
1234567 7654321

样例输出:

样例1
136062
样例2
1920693

提示:

样例1实际操作


2 738402 2023587
1 45991 325117
1 1097667 1357265
2 1992218 1832607
1 707808 1484463
2 1695666 1158822
2 1010062 313283
2 1577917 873894

对于100%的数据,1<=M<=3e6,1<=Seed<=1e8

时间限制: 2000ms
空间限制: 64MB