背景
她显得有些慌张。
「太,太好了」
「彼此都成了老婆婆,也许会偷偷觉得对方年轻的时候真好呢」
「我,不管你变成什么样子…… 我都,喜欢你」
「真的吗?那我现在变成老婆婆也可以吗?」
一阵深深的沉默。怎么看都是在认真的思考。她的正直和认真让我的眼梢舒缓了下来。
经过了花瓣积在脚下这么长的时间,一个羞涩的声音飘然传来。
「还是年轻的样子就好……」
「果然是这样啊」
「我也这样想」
我笑道。对方也像被吸引似的抬起头,安心地笑了。
两人相视而笑,突然,喉咙和眼睛在颤抖。
「又见到你了」
无法判断这句话是谁说的。
无论对于谁都是真心话。
不论是声音、语言,还是交谈过的一切,都让人觉得痒痒的。
不在记忆中的场所也没关系。
因为可以再次一起去任何地方。
「安达」 与 「岛村」
去大海吧。
海?
因为有了船,所以哪里都能去哦。
嗯,走吧。
无论去哪里,都是两人一起。

题目描述
岛村给了你一个长度为 n 的整数序列 a1,a2,⋯,an。
这个序列上经过了 m 个时刻。在其中第 i 个时刻,给定两个整数 li,ri,然后 ali,ali+1⋯,ari 全部分别变为了其在模 200003 意义下的乘法逆元。
记 ft(R) 为在第 t 个时刻结束时 a1,a2,⋯,aR 中不同数的个数。
岛村现在有 q 次询问,其中第 j 次询问给定 xj,yj。请你求出 $\sum _{r=1}^{x_j}\limits\sum _{i=1}^{y_j}\limits f_{i}(r)$。
输入格式
由于读入量过大,本题采用下发数据生成器的方式输入。
using namespace std;
const int N=2e5+3,Q=5e6+3;
int n,m,q,Amax,a[N];
int l[N],r[N],x[Q],y[Q];
unsigned sd,z1,z2,z3,z4;
unsigned rnd(){
sd=((z1<<6)^z1)>>13,z1=((z1&4294967294U)<<18)^sd;
sd=((z2<<2)^z2)>>27,z2=((z2&4294967288U)<<2)^sd;
sd=((z3<<13)^z3)>>21,z3=((z3&4294967280U)<<7)^sd;
sd=((z4<<3)^z4)>>12,z4=((z4&4294967168U)<<13)^sd;
return (z1^z2^z3^z4);
}
void reader(){
cin>>n>>m>>q>>sd>>Amax;
z1=sd,z2=(~sd)^0x233333333U;
z3=sd^0x1234598766U,z4=(~sd)+51;
for(int i=1;i<=n;++i){
a[i]=rnd()%Amax+1;
}
for(int i=1;i<=m;++i){
l[i]=rnd()%n+1,r[i]=rnd()%n+1;
if(l[i]>r[i])swap(l[i],r[i]);
}
for(int i=1;i<=q;++i){
x[i]=rnd()%n+1,y[i]=rnd()%m+1;
}
}
你需要在程序开头加入上述代码,输入时调用 reader() 即可。
其中变量的含义与题目描述中的变量相同。
我们保证正解与此读入方式无关。
输出格式
由于输出量过大。你只需输出一个数,表示所有询问答案的按位异或和。
我们保证正解与此输出方式无关。
5 5 5 5 5
52
432 54 543 4739 4325
5576625
15032 18004 300043 4739432 153425
1619361980175
111111 11111 555555 9 111111
29813834975008
提示
样例解释:
对于样例一:
每个时刻变换为逆元的区间依次为 [3,4],[1,5],[1,5],[4,5],[2,2]。
各个时刻下的序列 a 依次如下:
初始时:[3,2,3,3,4]。
第一次变化后:[3,2,66668,66668,4]。
第二次变化后:[66668,100002,3,3,50001]。
第三次变化后:[3,2,66668,66668,4]。
第四次变化后:[3,2,66668,3,50001]。
第五次变化后:[3,100002,66668,3,50001]。
各个 ft(R) 的值如下:
f1(1)=1,f1(2)=2,f1(3)=3,f1(4)=3,f1(5)=4,
f2(1)=1,f2(2)=2,f2(3)=3,f2(4)=3,f2(5)=4,
f3(1)=1,f3(2)=2,f3(3)=3,f3(4)=3,f3(5)=4,
f4(1)=1,f4(2)=2,f4(3)=3,f4(4)=3,f4(5)=4,
f5(1)=1,f5(2)=2,f5(3)=3,f5(4)=3,f5(5)=4。
各询问参数与答案如下:
第一次询问:x1=1,y1=3,答案为 3。
第二次询问:x2=4,y2=2,答案为 18。
第三次询问:x3=4,y3=4,答案为 36。
第四次询问:x4=5,y4=1,答案为 13。
第五次询问:x5=3,y5=2,答案为 12。
所以输出 3⊕18⊕36⊕13⊕12=52。
数据范围:
本题目采用子任务捆绑测试。
对于所有数据:1≤n≤2×105,1≤m≤2×104,1≤q≤5×106。
- ∀1≤i≤n,有 1≤ai<200003。
- ∀1≤j≤m,有 1≤lj≤rj≤n。
- ∀1≤k≤q,有 1≤xk≤n,1≤yk≤m。
::cute-table{tuack}
| 子任务编号 | n= | m= | q= | 分值 | 时间限制 |
|:-:|:-:|:-:|:-:|:-:| :-:|
| 0 | 10 | 10 | 10 | 5 | 1 秒 |
| 1 | 5000 | 5000 | 5000 | ^ | ^ |
| 2 | 104 | 104 | 104 | ^ | ^ |
| 3 | ^ | ^ | 106 | ^ | ^ |
| 4 | 2×105 | ^ | 2×105 | 15 | 3.5 秒 |
| 5 | ^ | 2×104 | ^ | ^ |^ |
| 6 | ^ | 104 | 2×106 | ^ |^ |
| 7 | ^ | 2×104 | ^ | ^ | ^ |
| 8 | ^ | ^ | 5×106 | 20 | ^ |