显然这个题不强制在线我们就有一个非常优秀的树剖做法

但是现在强制在线使得这个问题变得看起来有些难搞了

于是就变成了动态点分治的板子题了

我们先建一棵点分树，对于每一个分治重心我们存一下当前分治块内所有点到这个点的距离，用一个vector存下来

我们再存一下每个点作为分治重心的时分治块内部所有点上一级分治重心的距离

每次询问我们暴力跳点分树，在vector里二分即可

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define re register#define LL long long#define mp std::make_pair#define pb push_back#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=150005;typedef std::pair
         
           pii;struct E{int v,nxt,w;}e[maxn<<1];int n,num,m,S,rt,cnt,A;int head[maxn],pre[maxn],vis[maxn],fa[maxn],a[maxn];int deep[maxn],b[maxn<<1],sum[maxn],mx[maxn],pos[maxn];int f[maxn<<1][20],lg[maxn<<1];inline void add(int x,int y,int w) { e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;}std::vector
          
            son[maxn];std::vector
           
             sg[maxn],sh[maxn];std::vector
            
              g[maxn],h[maxn];void getpre(int x) { b[++cnt]=x;pos[x]=cnt; for(re int i=head[x];i;i=e[i].nxt) { if(deep[e[i].v]) continue; deep[e[i].v]=deep[x]+1,pre[e[i].v]=pre[x]+e[i].w; getpre(e[i].v);b[++cnt]=x; }}void getroot(int x,int f) { sum[x]=1;mx[x]=0; for(re int i=head[x];i;i=e[i].nxt) { if(vis[e[i].v]||f==e[i].v) continue; getroot(e[i].v,x);sum[x]+=sum[e[i].v]; mx[x]=max(mx[x],sum[e[i].v]); } mx[x]=max(S-sum[x],mx[x]); if(mx[x]
             
              >1; if(g[x][mid].first<=t) l=mid+1,c=mid; else r=mid-1; } if(c!=-1) tot-=c+1,ans-=sg[x][c];}inline int LCA(int x,int y) { x=pos[x],y=pos[y]; if(x>y) std::swap(x,y); int k=lg[y-x+1]; if(deep[f[x][k]]
              
               <
               
                >1; if(h[x][mid].first<=t) l=mid+1,c=mid; else r=mid-1; } if(c!=-1) tot=c+1,ans+=sh[x][c]; if(p) find(p,t,tot,ans); ans+=1ll*tot*dis(x,k); p=x;x=fa[x]; } return ans;}int main() { n=read(),m=read(),A=read(); for(re int i=1;i<=n;i++) a[i]=read(); for(re int x,y,w,i=1;i
                
                 >1]+1; for(re int j=1;j<=lg[2*n];j++) for(re int i=1;i+(1<
                 
                  <=2*n;i++) if(deep[f[i][j-1]]
                  
                   <<(j-1))][j-1]]) f[i][j]=f[i][j-1]; else f[i][j]=f[i+(1<<(j-1))][j-1]; mx[0]=n+1,S=n,rt=0,getroot(1,0);dfs(rt); LL lst=0;int u,x,y,l,r; while(m--) { u=read(),x=read(),y=read(); l=(1ll*x+lst)%A,r=(1ll*y+lst)%A; if(l>r) std::swap(l,r); printf("%lld\n",lst=ask(u,r)-ask(u,l-1)); } return 0;}