解题：洛谷4135 作诗

  1 // luogu-judger-enable-o2
  2 #include<cmath>
  3 #include<cstdio>
  4 #include<cctype>
  5 #include<vector>
  6 #include<cstring>
  7 #include<algorithm>
  8 using namespace std;
  9 const int N=100005,Sq=1400;
 10 int eve[Sq][Sq],exi[N];
 11 int a[N],blo[N],pts[Sq][2];
 12 int n,m,c,t1,t2,t3,t4,sqr,cnt,ans,lans;
 13 vector<int> pos[N];
 14 inline int read()
 15 {
 16     int ret=0;
 17     char ch=getchar();
 18     while(!isdigit(ch))
 19         ch=getchar();
 20     while(isdigit(ch))
 21         ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
 22     return ret;
 23 }
 24 void write(int x)
 25 {
 26     if(x>9) write(x/10);
 27     putchar(x%10+48);
 28 }
 29 inline int ask(int l,int r,int v)
 30 {
 31     if(l>r) return 0;
 32     vector<int>::iterator ll=lower_bound(pos[v].begin(),pos[v].end(),l);
 33     vector<int>::iterator rr=upper_bound(pos[v].begin(),pos[v].end(),r);
 34     return rr-ll; 
 35 }
 36 int main() 
 37 {
 38     register int i,j;
 39     n=read(),c=read(),m=read(),pts[cnt=1][0]=1;
 40     sqr=sqrt((double)n/((log(n)/log(2))));
 41     for(int i=1;i<=n;i++)
 42     {
 43         a[i]=read();
 44         blo[i]=(i-1)/sqr+1;
 45         pos[a[i]].push_back(i);
 46         if(i%sqr==0)
 47         {
 48             pts[cnt++][1]=i;
 49             pts[cnt][0]=i+1;
 50         }
 51     }
 52     pts[cnt][1]=n;
 53     for(i=1;i<=cnt;i++)
 54     {
 55         int tmp=0;
 56         for(j=pts[i][0];j<=n;j++)
 57         {
 58             if(exi[a[j]])
 59                 (exi[a[j]]%2)?tmp++:tmp--;
 60             exi[a[j]]++,eve[i][blo[j]]=tmp;
 61         }
 62         memset(exi,0,sizeof exi);
 63     }
 64     while(m--)
 65     {
 66         t1=read(),t2=read();
 67         t1=(t1+lans)%n+1,t2=(t2+lans)%n+1;
 68         if(t1>t2) swap(t1,t2); ans=0,t3=blo[t1],t4=blo[t2]; 
 69         if(t3!=t4)
 70         {
 71             ans+=eve[t3+1][t4-1];
 72             int ll=pts[t3+1][0],rr=pts[t4-1][1];
 73             for(i=t1;i<=pts[t3][1];i++)
 74                 if(!exi[a[i]])
 75                 {
 76                     exi[a[i]]=true;
 77                     int cnt1=ask(t1,t2,a[i]),cnt2=ask(ll,rr,a[i]);
 78                     if(cnt1%2==0) ans+=(cnt2%2||!cnt2);
 79                     else if(cnt2%2==0&&cnt2) ans--; 
 80                 }
 81             for(i=pts[t4][0];i<=t2;i++)
 82                 if(!exi[a[i]])
 83                 {
 84                     exi[a[i]]=true;
 85                     int cnt1=ask(t1,t2,a[i]),cnt2=ask(ll,rr,a[i]);
 86                     if(cnt1%2==0) ans+=(cnt2%2||!cnt2);
 87                     else if(cnt2%2==0&&cnt2) ans--; 
 88                 }
 89             for(i=t1;i<=ll-1;i++) exi[a[i]]=0;
 90             for(i=rr+1;i<=t2;i++) exi[a[i]]=0;
 91         }
 92         else
 93         {
 94             for(i=t1;i<=t2;i++)
 95             {
 96                 if(exi[a[i]]) 
 97                     (exi[a[i]]%2)?ans++:ans--;
 98                 exi[a[i]]++;
 99             }
100             for(i=t1;i<=t2;i++) exi[a[i]]=0;
101         }
102         write(lans=ans),puts("");
103     }
104     return 0;
105 }