题目

给定一个数列 \(a\)，维护以下两种操作

1. 区间取平方 \(a[i]=a[i]^2\bmod p\)
2. 区间和（不取模）

\(p\) 为给定的小于 \(10^4\) 的数，\(n\leq 10^5\)

分析

由于这个模数比较小，不妨猜想它最终会以某种形式结束。

但是不是结束在一个数，可能最后进入一个循环节。

所以在线段树上维护这个区间的循环节循环到第几个位置。

可以发现循环节大小最多为 \(60\)，那么时间复杂度为 \(O(60n\log{n})\)

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=100011; bool loop[N<<2],cir[N]; int lcm[71][71]; queueq;
int w[N<<2][71],len[N<<2],nxt[N],a[N],pos[N<<2],n,m,mod,lazy[N<<2],deg[N];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
void Get(int k,int x){
	loop[k]=cir[x],w[k][pos[k]=0]=x,len[k]=1;
	if (loop[k]){
		for (int y=nxt[x];y!=x;y=nxt[y])
		    w[k][len[k]++]=y;
	}
}
void pup(int k){
	loop[k]=loop[k<<1]&loop[k<<1|1],pos[k]=0;
	len[k]=lcm[len[k<<1]][len[k<<1|1]];
	int t0=pos[k<<1],t1=pos[k<<1|1];
	for (int i=0;i>1;
    build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pup(k);
}
void update(int k,int l,int r,int x,int y){
	if (x<=l&&r<=y&&loop[k]) {ptag(k,1); return;}
	if (l==r) {a[l]=nxt[a[l]],Get(k,a[l]); return;}
	int mid=(l+r)>>1;
	if (lazy[k]){
		ptag(k<<1,lazy[k]);
		ptag(k<<1|1,lazy[k]);
		lazy[k]=0;
	}
	if (x<=mid) update(k<<1,l,mid,x,y);
	if (y>mid) update(k<<1|1,mid+1,r,x,y);
	pup(k);
}
int query(int k,int l,int r,int x,int y){
	if (l==x&&r==y) return w[k][pos[k]];
	int mid=(l+r)>>1;
	if (lazy[k]){
		ptag(k<<1,lazy[k]);
		ptag(k<<1|1,lazy[k]);
		lazy[k]=0;
	}
	if (y<=mid) return query(k<<1,l,mid,x,y);
    else if (x>mid) return query(k<<1|1,mid+1,r,x,y);
	    else return query(k<<1,l,mid,x,mid)+query(k<<1|1,mid+1,r,mid+1,y);
}
int main(){
	n=iut(),m=iut(),mod=iut();
	for (int i=1;i<71;++i)
	for (int j=1;j<71;++j)
	    lcm[i][j]=i*j/__gcd(i,j);
	for (int i=0;i