33OJ
登录 注册

#P17630. 安达与岛村

安达与岛村

背景

她显得有些慌张。

「太,太好了」
「彼此都成了老婆婆,也许会偷偷觉得对方年轻的时候真好呢」
「我,不管你变成什么样子…… 我都,喜欢你」
「真的吗?那我现在变成老婆婆也可以吗?」

一阵深深的沉默。怎么看都是在认真的思考。她的正直和认真让我的眼梢舒缓了下来。

经过了花瓣积在脚下这么长的时间,一个羞涩的声音飘然传来。

「还是年轻的样子就好……」
「果然是这样啊」
「我也这样想」

我笑道。对方也像被吸引似的抬起头,安心地笑了。
两人相视而笑,突然,喉咙和眼睛在颤抖。

「又见到你了」

无法判断这句话是谁说的。
无论对于谁都是真心话。

不论是声音、语言,还是交谈过的一切,都让人觉得痒痒的。

不在记忆中的场所也没关系。
因为可以再次一起去任何地方。

「安达」 与 「岛村」

去大海吧。
海?

因为有了船,所以哪里都能去哦。
嗯,走吧。

无论去哪里,都是两人一起。

题目描述

岛村给了你一个长度为 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() 即可。

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

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

输出格式

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

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

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][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。

::cute-table{tuack} | 子任务编号 | n=n= | m=m= | q=q= | 分值 | 时间限制 | |:-:|:-:|:-:|:-:|:-:| :-:| | 00 | 1010 | 1010 | 1010 | 55 | 11 秒 | | 11 | 50005000 | 50005000 | 50005000 | ^ | ^ | | 22 | 10410^4 | 10410^4 | 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 | ^ |