Sequence Ⅱ

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int mx = 2e5+5;
#define mid (L+R)/2
struct node{
  int ls,rs;
  int sum;
}T[50*mx];
int sz;
int root[mx];
void built(int &rt,int L,int R){
  rt = sz++;
  T[sz].sum = 0;
  if(L==R)
    return;
  built(T[sz].ls,L,mid);
  built(T[sz].rs,mid+1,R);
}
void creat(int &rt,int x,int L,int R,int p,int v){
  rt = sz++;                                         //新的结点
  T[rt] = T[x];                                      //新节点的左右儿子初始化前一棵树的数据
  T[rt].sum+=v;                                      //插了1个数，在前一棵树的相同结点加v
  if(L==R)                                           //递归到叶节点回去
    return;
  if(p<=mid) creat(T[rt].ls,T[x].ls,L,mid,p,v);
  else creat(T[rt].rs,T[x].rs,mid+1,R,p,v);
}
int query(int end,int rt,int L,int R){ //
  if(R<=end)                                         //全覆盖
    return T[rt].sum;                                //返回权值
  if(mid<end) return T[T[rt].ls].sum+query(end,T[rt].rs,mid+1,R);      //左子树权值 + 右区间返回值
  else return query(end,T[rt].ls,L,mid);             //递归左区间
}
int Query(int end,int rt,int L,int R,int k){
  if(L==R)                                          //L==R那么肯定是位置在L
    return L;
  int s = T[T[rt].ls].sum;
  if(s<k) return Query(end,T[rt].rs,mid+1,R,k-s);   //在右子树，k减去左子树的s
  else return Query(end,T[rt].ls,L,mid,k);          //大于等于(k+1)/2个不同的数那么第一个位置肯定在左子树
}
map<int,int>mp;                                    //第一个是键的类型，第二个是值的类型，key自动排序，但是key的唯一性，会只保留一个
int ans[mx];                                       //输出
int a[mx];                                         //输入
int main(){
  int t;
  scanf("%d",&t);                                 //实例个数
  int ca = 1;
  int n,m;
  while(t--){
    scanf("%d%d",&n,&m);                         //实例长度、操作次数
    sz = 0;
    int tmp;
    built(root[n+1],1,n);                        //建立原始空树
    mp.clear();
    for(int i = 1; i <= n; i++)                  //读取序列
      scanf("%d",&a[i]);
    for(int i = n; i >= 1; i--)                 //倒序插入
      if(!mp[a[i]]){                            //插入新的key
        creat(root[i],root[i+1],1,n,i,1);
        mp[a[i]] = i;
      }
      else{                                     //重复的key
        creat(tmp,root[i+1],1,n,mp[a[i]],-1);   //先去掉旧的权值
        creat(root[i],tmp,1,n,i,1);             //再更新新的权值
        mp[a[i]] = i;                           //更新key的数值
      }
    printf("Case #%d: ",ca++);
    for(int j = 1; j <= m; j++){                //输出
      int l,r;
      scanf("%d%d",&l,&r);                      //左右区间排序
      l = (l+ans[j-1])%n+1;                     //(Li + ans-1) mod n + 1
      r = (r+ans[j-1])%n+1;                     //(Ri + ans-1) mod n + 1
      // cout<<l<<r<<endl;
      if(l>r)
        swap(l,r);                              //左右区间排序
      int k = query(r,root[l],1,n);             //子序列右区间、子序列左区间的根节点，序列左区间、序列右区间：返回子序列的k值
      //cout<<k<<endl;
      k = Query(r,root[l],1,n,(k+1)/2);         //返回序列的k值
      ans[j] = k;
      printf("%d%c",k,j==m?'\n':' ');
    }
  }
  return 0;
}