卡常线段树模板
提交数: 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