#P17776. 安达与岛村

安达与岛村

题目描述

岛村给了你一个长度为 nn 的整数序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。

这个序列上经过了 mm 个时刻。在其中第 ii 个时刻,给定两个整数 li,ril_i,r_i,然后 ali,ali+1⋯ ,aria_{l_i},a_{l_i+1}\cdots , a_{r_i} 全部分别变为了其在模 200003200003 意义下的乘法逆元。

记 ft(R)f_t(R) 为在第 tt 个时刻结束时 a1,a2,⋯ ,aRa_1,a_2,\cdots ,a_{R} 中不同数的个数。

岛村现在有 qq 次询问,其中第 jj 次询问给定 xj,yjx_j,y_j。请你求出 $\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() 即可。

其中变量的含义与题目描述中的变量相同。

我们保证正解与此读入方式无关。

输出格式

由于输出量过大。你只需输出一个数,表示所有询问答案的按位异或和。

我们保证正解与此输出方式无关。

输入输出样例 #1

输入 #1

5 5 5 5 5

输出 #1

52

输入输出样例 #2

输入 #2

432 54 543 4739 4325

输出 #2

5576625

输入输出样例 #3

输入 #3

15032 18004 300043 4739432 153425

输出 #3

1619361980175

输入输出样例 #4

输入 #4

111111 11111 555555 9 111111

输出 #4

29813834975008

说明/提示

样例解释:

对于样例一:

每个时刻变换为逆元的区间依次为 [3,4],[1,5],[1,5],[4,5],[2,2][3,4],[1,5],[1,5],[4,5],[2,2]。

各个时刻下的序列 aa 依次如下:

初始时:[3,2,3,3,4][3,2,3,3,4]。
第一次变化后:[3,2,66668,66668,4][3,2,66668,66668,4]。
第二次变化后:[66668,100002,3,3,50001][66668,100002,3,3,50001]。
第三次变化后:[3,2,66668,66668,4][3,2,66668,66668,4]。
第四次变化后:[3,2,66668,3,50001][3,2,66668,3,50001]。
第五次变化后:[3,100002,66668,3,50001][3,100002,66668,3,50001]。

各个 ft(R)f_t(R) 的值如下:

f1(1)=1,f1(2)=2,f1(3)=3,f1(4)=3,f1(5)=4,f_1(1)=1,f_1(2)=2,f_1(3)=3,f_1(4)=3,f_1(5)=4,
f2(1)=1,f2(2)=2,f2(3)=3,f2(4)=3,f2(5)=4,f_2(1)=1,f_2(2)=2,f_2(3)=3,f_2(4)=3,f_2(5)=4,
f3(1)=1,f3(2)=2,f3(3)=3,f3(4)=3,f3(5)=4,f_3(1)=1,f_3(2)=2,f_3(3)=3,f_3(4)=3,f_3(5)=4,
f4(1)=1,f4(2)=2,f4(3)=3,f4(4)=3,f4(5)=4,f_4(1)=1,f_4(2)=2,f_4(3)=3,f_4(4)=3,f_4(5)=4,
f5(1)=1,f5(2)=2,f5(3)=3,f5(4)=3,f5(5)=4f_5(1)=1,f_5(2)=2,f_5(3)=3,f_5(4)=3,f_5(5)=4。

各询问参数与答案如下:

第一次询问:x1=1,y1=3x_1=1,y_1=3,答案为 33。
第二次询问:x2=4,y2=2x_2=4,y_2=2,答案为 1818。
第三次询问:x3=4,y3=4x_3=4,y_3=4,答案为 3636。
第四次询问:x4=5,y4=1x_4=5,y_4=1,答案为 1313。
第五次询问:x5=3,y5=2x_5=3,y_5=2,答案为 1212。

所以输出 3⊕18⊕36⊕13⊕12=523 \oplus 18 \oplus 36 \oplus 13 \oplus 12=52。


数据范围:

本题目采用子任务捆绑测试。

对于所有数据:1≤n≤2×1051 \le n \le 2 \times 10^5,1≤m≤2×1041 \le m \le 2 \times 10^4,1≤q≤5×1061 \le q \le 5 \times 10^6。

  • ∀1≤i≤n\forall 1 \le i \le n,有 1≤ai<2000031 \le a_i < 200003。
  • ∀1≤j≤m\forall 1 \le j \le m,有 1≤lj≤rj≤n1 \le l_j \le r_j \le n。
  • ∀1≤k≤q\forall 1 \le k \le q,有 1≤xk≤n1 \le x_k \le n,1≤yk≤m1 \le y_k \le m。
子任务编号 n=n= m=m= q=q= 分值 时间限制
00 1010 55 11 秒
11 50005000 ^
22 10410^4
33 ^ ^ 10610^6
44 2×1052 \times 10^5 2×1052 \times 10^5 1515 3.53.5 秒
55 ^ 2×1042 \times 10^4 ^ ^ ^
66 10410^4 2×1062 \times 10^6
77 2×1042 \times 10^4 ^
88 ^ 5×1065 \times 10^6 2020