OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【THOI2015】平方运算

【题目描述】

小H是一位勤奋的中学生,他的理想是进入自己心仪的大学学习计算机专业。为了实现这一目标。他从小就开始认真学习信息学竞赛的基础知识。

今天,小H学习了平方运算。为了检验自己是否熟练掌握了平方运算,小H决定给自己出一道题。小H有一个长度为N的序列{X1,X2,...,Xn}。小H会时不时地取出序列中的一段连续区间[l,r],并将其中的每一个数改为原数值的平方对p取模的结果,即:


其中,p为某个给定的数。为了检验自己的运算是否正确,小H还会时不时地想要知道序列中某一段连续区间[l,r]内所有数的和是多少。

但是,小H现在并没有标准答案。所以,他向你求助,希望你编写一个程序,帮他计算出每次想要知道的区间内的数的和。

【输入】

第一行有三个整数N,M,p,分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。

接下来一行N个数代表一开始的序列{X1,X2,...,Xn}。

接下来M行,每行三个整数op,l,r。其中op代表本次操作的类型。若op=0,代表这是一次平方操作,平方的区间为[l,r];如果op=1,代表这是一次询问操作,询问的区间为[l,r]。

【输出】

对于每次的询问操作,输出一行代表这段区间内数的总和。注意:答案没有对任何数取模。

【输入样例】

3 3 11

1 2 3

1 1 3

0 1 3

1 1 3

【输出样例】

6

14

【数据范围】

1<=N,M<=100000

p∈{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977}

【题解】

线段树,区间平方,区间求和,一看就不可做。

但我们观察到模数十分带感,首先我们知道平方操作在模p剩余系下一定会出现循环,且循环节大小不会超过p,这启发我们去进一步挖掘p的性质。经过验证可以得到,对于给出的p,所有小于p的数的平方循环节最小公倍数其实都不超过60!于是我们可以在线段树每个节点记录一个长度为循环节最小公倍数的数组,记录每一次平方后这个区间的和,这样就能快速维护信息了。修改时需要一个lazy标记,每次修改后都要重新计算这个数组。

最后的复杂度是O(nrlog(n)),其中r是循环节最小公倍数。即使每一步都要重新计算数组,这个复杂度也能够得到保证。具体的找循环节的方法太多,也比较简单,此处不再赘述。

【代码】

赛后AC系列……

http://paste.ubuntu.com/11538789/

评论

© OI技术宅 | Powered by LOFTER