P4681 [THUSC2015]平方运算（题解）

· · 题解

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;
}