CF2153F

xujindong_ · 2025-10-14 20:45:23 · 题解

考虑这个神秘的限制是说不存在 x,y,x,y。若 a_l=a_r，则 (l,r) 内的数都不会出现在其他位置，形成一个嵌套关系。

我们可以考虑建出一个树形结构，将每种数以第一次出现为根连成一个菊花，数之间按嵌套关系连边。具体来说，维护一个栈，每次将当前位置连向栈顶，然后若它是第一次出现就入栈，若它是最后一次出现就出栈。这样的一棵树刻画了数的嵌套关系，其 DFS 序是原序列，每种相同的数构成菊花，且非第一次出现的数都是叶子。这也说明大小 >1 的子树都是独立的。

现在考虑区间询问对应到 DFS 序。特判 l=r，设 u 为 LCA 的子节点是 l 的祖先，v 为 LCA 的子节点是 r 的祖先，u' 是 l 子树里编号最大的节点。则 [l,r] 可以分成 [l,u'],(u',v),[v,r] 三部分。特别地，若 l 是 r 的祖先，前两部分不存在。

单独算值等于 LCA 的点的奇偶性。对于 [l,u']，我们可以差分成 [l,n]-(u'+1,n]，(u'+1,n] 和 [l,u'] 没有重复数，预处理后缀的答案即可。[u,r] 同理可以差分成两个前缀。特别地，如果 l/r 是值等于 LCA 的单点，要记上。

对于 (u',v)，就是 LCA 连续的几棵子树。因为每个数都是菊花的性质，容易求出每棵子树的答案，去掉值等于 LCA 的单点后这些子树也是独立的，可以直接加。对每个节点的所有儿子预处理一个前缀和即可。还要统计值恰好等于 LCA 的数，这个也可以对兄弟预处理前缀和。

瓶颈是树上 k 级祖先，O(n+q\log n)。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[500005],visl[500005],visr[500005],st[500005],top,ft[500005][20],dep[500005],sz[500005],sib[500005],nxt[500005];
long long pre[500005],suf[500005],sum[500005],ans[500005];
bool o[500005],num[500005];
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>t;
  while(t--){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],visr[a[i]]=i,pre[i]=pre[i-1]+(o[a[i]]?-a[i]:a[i]),o[a[i]]^=1;
    for(int i=1;i<=n;i++)o[i]=0;
    for(int i=n;i>=1;i--)visl[a[i]]=i,suf[i]=suf[i+1]+(o[a[i]]?-a[i]:a[i]),o[a[i]]^=1;
    for(int i=1;i<=n;i++){
      ft[i][0]=st[top],dep[i]=dep[st[top]]+1,sz[i]=1;
      for(int j=1;j<=__lg(dep[i]);j++)ft[i][j]=ft[ft[i][j-1]][j-1];
      if(i==visl[a[i]])st[++top]=i;
      if(i==visr[a[i]])top--;
    }
    for(int i=n;i>=1;i--){
      int fa=ft[i][0];
      if(a[i]!=a[fa])sum[i]+=o[a[i]]*a[i];
      sz[fa]+=sz[i],sum[fa]+=sum[i],sum[i]+=sum[sib[fa]],num[i]=num[sib[fa]]^(a[i]==a[fa]),nxt[i]=sib[fa],sib[fa]=i;
    }
    for(int i=1,l,r;i<=m;i++){
      cin>>l>>r,l=(l+ans[i-1]-1)%n+1,r=(r+ans[i-1]-1)%n+1;
      if(l>r)swap(l,r);
      if(l==r){
        ans[i]=a[l];
        continue;
      }
      int lca,u=l,v=r;
      while(dep[u]>dep[v])u=ft[u][__lg(dep[u]-dep[v])];
      while(dep[v]>dep[u])v=ft[v][__lg(dep[v]-dep[u])];
      if(u==v)lca=u;
      else{
        for(int i=__lg(dep[u]);i>=0;i--)if(dep[u]>1<<i&&ft[u][i]!=ft[v][i])u=ft[u][i],v=ft[v][i];
        lca=ft[u][0];  
      }
      if(l==lca)ans[i]=pre[r]-pre[l-1];
      else{
        ans[i]=0;
        bool type=0;
        if(a[l]==a[lca])type^=1;
        else ans[i]+=suf[l]-suf[u+sz[u]];
        ans[i]+=sum[nxt[u]]-sum[v],type^=num[nxt[u]]^num[v];
        if(a[r]==a[lca])type^=1;
        else ans[i]+=pre[r]-pre[v-1];
        if(type)ans[i]+=a[lca];
      }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<(i==m?'\n':' ');
    for(int i=0;i<=n;i++)sum[i]=sib[i]=o[i]=num[i]=0;
    top=0;
  }
  return 0;
}