本文共 2811 字，大约阅读时间需要 9 分钟。

题意

题解

我们可以发现，强制在线的模数很小。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;const int N=50005*2;int n,m,key;int bk;int read(){      int x=0; char ch=getchar();      while (ch<'0' || ch>'9') ch=getchar();      while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }      return x;  }int a[N];int b[N];//排序且去重后的数组 int rk[N];//排行第几 int rt;struct qt{    int x,y,last;}e[N];int num,last[N];void init (int x,int y){    num++;    e[num].x=x;e[num].y=y;    e[num].last=last[x];    last[x]=num;}int L[N],R[N],cnt=0,cnt1=0;//dfs序int id[N];int dep[N],ys[N],top[N],tot[N],fa[N],son[N];void dfs1 (int x,int ff){    tot[x]=1;    for (int u=last[x];u!=-1;u=e[u].last)    {        int y=e[u].y;        dep[y]=dep[x]+1;        fa[y]=x;        dfs1(y,x);        tot[x]+=tot[y];        if (tot[son[x]]
        
         dep[ty]) {swap(x,y);swap(tx,ty);} while (tx!=ty) { y=fa[ty]; ty=top[y]; if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);} } if (dep[x]>dep[y]) swap(x,y); return x;}struct qq{ int x,y,id;//两个点的编号 第几个询问 }s[N];void Ins (int x,int y)//加入一个这个询问 { cnt++; if (L[x]>L[y]) swap(x,y); //x的比较小 int LCA=get_LCA(x,y); s[cnt]={(LCA==x)?L[x]:R[x],L[y],cnt};}bool cmp (qq a,qq b){ return ((a.x/bk)==(b.x/bk))?a.y
         
          
           =1) { lalal=lalal+c0[x]; x=x-lb(x); } return lalal; }LL get_tot (LL x){ LL lalal=0; while (x>=1) { lalal=lalal+c1[x]; x=x-lb(x); } return lalal;}void change (LL x,int xx,LL op){ while (xx<=b[0]) { c0[xx]+=(x*op); c1[xx]+=op; xx+=lb(xx); }}void Add (int x)//我们加入当前这个点 { int xx=rk[x];//得到真实排名 if (in[x]==false)//我们要加上这个点 { Ans=Ans+get_sum(xx); LL tot=get_tot(b[0])-get_tot(xx)+1; Ans=Ans+(LL)a[x]*tot; change(b[xx],xx,1); in[x]=true; } else//删除这个点 { change(b[xx],xx,-1); Ans=Ans-get_sum(xx); LL tot=get_tot(b[0])-get_tot(xx)+1; Ans=Ans-tot*(LL)a[x]; in[x]=false; }}LL ans[N];int find (int x){ int l=1,r=b[0]; while (l<=r) { int mid=(l+r)>>1; if (b[mid]==x) return mid; else if (b[mid]>x) r=mid-1; else l=mid+1; }}void prepare (){ sort(b+1,b+1+n);b[0]=1; for (int u=2;u<=n;u++) if (b[u]!=b[b[0]]) b[++b[0]]=b[u]; for (int u=1;u<=n;u++) rk[u]=find(a[u]);}int main(){ num=0;memset(last,-1,sizeof(last)); n=read();m=read();key=read(); bk=(int)sqrt(2*n); for (int u=1;u<=n;u++) a[u]=read(),b[u]=a[u]; prepare(); for (int u=1;u<=n;u++) { int x; x=read(); if (x==0) rt=u; else init(x,u); } dep[rt]=1;dfs1(rt,0);dfs(rt,rt); int x=1; cnt=0; for (int u=1;u<=m;u++) { char ss[5]; scanf("%s",ss); if (ss[0]=='C') x=read(); else { int y=read(); Ins(x,y%n+1); Ins(x,(y+key)%n+1); } } sort(s+1,s+1+cnt,cmp); memset(in,false,sizeof(in)); int l=1,r=0; for (int u=1;u<=cnt;u++) { while (s[u].x
           
            r) Add(id[++r]); while (s[u].x>l) Add(id[l++]); while (s[u].y