自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 22:02:35，当前版本为作者最后更新于2021-04-13 08:18:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P.S.

高质量好数据结构。
一直拍挂
对拍建议 $n=2,m=100000$ 这样调试难度低一点 qwq。
目前最优解看人头 rank2，不过我这种写法应该会自带大常数。

Description.

维护序列，要求支持：区间平方修改为模 $P$，查寻区间和。

Solution.

首先，我们发现，平方运算具有循环节。
打个表会发现题目中所有模下，循环节长度 $\text{lcm}$ 最大值为 $60$。
那么我们就可以考虑直接暴力，如果进入循环节了就直接开桶修改。
然后就做完了欸。
注意是区间修改，必须要打 lazetag。
注意无法预处理一个区间的答案，因为这个区间的子区间可能会被操作。
具体看代码及其注释吧

Coding.

//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}/*}}}*/
int n,m,P,a[100005],deg[10005];char v[10005];
struct segm{int smt,nw,sm[61],lz;char tag;}T[400005];
//tag代表当前区间是否全部进入循环节
//smt代表当前区间桶的循环节（为0代表未进入循环节
//sm表示桶，nw表示当前在桶中位置
//lz表示lazetag
//如果未进入循环节 sm[0] 表示当前这个点的权值
inline int gcd(int a,int b) {return b?gcd(b,a%b):a;}
inline int sqr(int x) {return x*x%P;}
inline void pushup(int x)
{
	T[x].tag=T[x<<1].tag&T[x<<1|1].tag;
	if(!T[x].smt) T[x].sm[0]=T[x<<1].sm[T[x<<1].nw]+T[x<<1|1].sm[T[x<<1|1].nw];
	if(T[x<<1].smt&&T[x<<1|1].smt)
	{
		int nl=T[x<<1].smt,nr=T[x<<1|1].smt,lw=T[x<<1].nw,rw=T[x<<1|1].nw;
		T[x].smt=nl/gcd(nl,nr)*nr,T[x].nw=0;//公共循环节长度是 lcm
		for(int i=0;i<T[x].smt;i++) T[x].sm[i]=T[x<<1].sm[(i+lw)%nl]+T[x<<1|1].sm[(i+rw)%nr];
		//把两个桶合并，注意两边不一定从起点开始，可能已经移动过了。  
	}
}
inline void allc(int x,int c) {T[x].nw=(T[x].nw+c)%T[x].smt,T[x].lz+=c;}
inline void pushdw(int x) {if(T[x].lz) allc(x<<1,T[x].lz),allc(x<<1|1,T[x].lz),T[x].lz=0;}
inline void INIT(int x)
{//预处理一个结点的桶信息
	for(int i=1;i<=60;i++)
	{
		T[x].sm[i]=sqr(T[x].sm[i-1]);//找到循环节
		if(T[x].sm[i]==T[x].sm[0]) {T[x].smt=i;break;}
	}
}
inline void build(int x,int l,int r)
{//无难点，不解释
	if(l==r) return T[x].sm[T[x].smt=0]=a[l],void();
	build(x<<1,l,(l+r)>>1),build(x<<1|1,((l+r)>>1)+1,r),pushup(x);
}
inline void modif(int x,int l,int r,int dl,int dr)
{
	if(l>dr||dl>r) return;else if(dl>l||r>dr)
		return pushdw(x),modif(x<<1,l,(l+r)>>1,dl,dr),modif(x<<1|1,((l+r)>>1)+1,r,dl,dr),pushup(x);
	//如果小区间和大区间无包含关系，那就正常线段树处理。  
	if(T[x].tag) return allc(x,1),void();//如果已经进入循环节，直接打lazetag
	if(l^r) return pushdw(x),modif(x<<1,l,(l+r)>>1,dl,dr),modif(x<<1|1,((l+r)>>1)+1,r,dl,dr),pushup(x);
	//没进入循环节还不是叶结点，只能暴力向下
	if(v[T[x].sm[0]]) return T[x].sm[0]=sqr(T[x].sm[0]),void();
	//如果还在循环节外面，那就暴跳，否则就预处理了
	if(!T[x].tag) INIT(x),T[x].tag=1,T[x].nw=1%T[x].smt;else T[x].nw=(T[x].nw+1)%T[x].smt;
}
inline int query(int x,int l,int r,int dl,int dr)
{//无难点，不解释
	if(dl>r||l>dr) return 0;else if(dl<=l&&r<=dr) return T[x].sm[T[x].nw];else pushdw(x);
	return query(x<<1,l,(l+r)>>1,dl,dr)+query(x<<1|1,((l+r)>>1)+1,r,dl,dr);
}
int main()
{
	read(n),read(m),read(P);queue<int>q;
	for(int i=0;i<P;i++) deg[sqr(i)]++;
	for(int i=0;i<P;i++) if(!deg[i]) q.push(i);
	while(!q.empty())
	{
		int x=q.front();q.pop(),v[x]=1;
		if(!--deg[sqr(x)]) q.push(sqr(x));
	}//topo找环
	for(int i=1;i<=n;i++) read(a[i]);
	for(build(1,1,n);m--;)
	{
		int op,l,r;read(op),read(l),read(r);
		if(op&1) modif(1,1,n,l,r);else printf("%d\n",query(1,1,n,l,r));
	}
	return 0;
}