练手题

LCT板子套线段树2

/*@Date    : 2019-07-15 18:57:11@Author  : Adscn (adscn@qq.com)@Link    : https://www.cnblogs.com/LLCSBlog*/#include
    
     using namespace std;#define IL inline#define RG register#define gi getint()#define gc getchar()#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)IL int getint(){    RG int xi=0;    RG char ch=gc;    bool f=0;    while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;    while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;    return f?-xi:xi;}template
     
      IL void pi(T k,char ch=0){    if(k<0)k=-k,putchar('-');    if(k>=10)pi(k/10,0);    putchar(k%10+'0');    if(ch)putchar(ch);}const unsigned int N=100007,mod=51061;namespace LCT{    int f[N],c[N][2],siz[N];    unsigned int val[N],lzya[N],lzym[N],ret[N];    bool rev[N];    inline bool ws(int x,int p){return c[p][1]==x;}    inline bool nroot(int x){return c[f[x]][0]==x||c[f[x]][1]==x;}    inline void pushup(int x)    {        ret[x]=(ret[c[x][0]]+ret[c[x][1]]+val[x])%mod;        siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;    }    inline void pushr(int x){if(x)swap(c[x][0],c[x][1]),rev[x]^=1;}    inline void pusha(int x,unsigned int av)    {        if(!x)return;        (val[x]+=av)%=mod;        (ret[x]+=(av*siz[x])%mod)%=mod;        (lzya[x]+=av)%=mod;    }    inline void pushm(int x,unsigned int mv)    {        if(!x)return;        (val[x]*=mv)%=mod;        (ret[x]*=mv)%=mod;        (lzya[x]*=mv)%=mod;        (lzym[x]*=mv)%=mod;    }    inline void pushdown(int x)    {        if(rev[x])pushr(c[x][0]),pushr(c[x][1]),rev[x]=0;        if(lzym[x]!=1)pushm(c[x][0],lzym[x]),pushm(c[x][1],lzym[x]),lzym[x]=1;        if(lzya[x])pusha(c[x][0],lzya[x]),pusha(c[x][1],lzya[x]),lzya[x]=0;    }    inline void pushdownall(int x)    {        if(nroot(x))pushdownall(f[x]);        pushdown(x);    }    inline void rotate(int x)    {        int p=f[x],g=f[p];        int t=ws(x,p);        int w=c[x][!t];        if(nroot(p))c[g][ws(p,g)]=x;c[p][t]=c[x][!t];c[x][!t]=p;        if(w)f[w]=p;f[p]=x;f[x]=g;        pushup(p);    }    inline void Splay(int x)    {        pushdownall(x);        while(nroot(x))        {            int p=f[x],g=f[p];            if(nroot(p))rotate(ws(x,p)^ws(p,g)?x:p);            rotate(x);        }        pushup(x);    }    inline void access(int x)    {        for(int y=0;x;x=f[y=x])        {            Splay(x);            c[x][1]=y;            pushup(x);        }    }    inline void makert(int x)    {        access(x);        Splay(x);        pushr(x);    }    inline void split(int x,int y)    {        makert(x);        access(y);        Splay(y);    }    inline int findrt(int x)    {        access(x),Splay(x);        pushdown(x);        while(c[x][0])pushdown(x=c[x][0]);        return x;    }    inline void link(int x,int y)    {        makert(x);        if(findrt(x)^y)f[x]=y;    }    inline void cut(int x,int y)    {        makert(x);        if(findrt(y)==x&&siz[x]<=2)f[y]=c[x][1]=0;    }}using namespace LCT;int main(void){    int n=gi,q=gi;    for(int i=1;i<=n;++i)siz[i]=lzym[i]=val[i]=1;    for(int i=1;i