51nod1471 小S的兴趣

题目来源： CodeForces

基准时间限制：1.5 秒空间限制：131072 KB 分值: 320

小S喜欢有趣的事。但是，每个人的兴趣都是独特的。小S热衷于自问自答。有一天，小S想出了一个问题。

有一个包含n个正整数的数组a和针对这个数组的几个问题。这些问题有两种类型：

1. 在数组下标l到r的部分上，将一个单元格循环移动到右端。即以下面方式重新分配数组上的元素。

a[l], a[l+1], ..., a[r-1], a[r] → a[r], a[l], a[l+1], ..., a[r-1].

2. 在数组下标l到r的部分上，计算有多少元素的值与k相等。

小S很喜欢这个问题并且很快解决了它，你是否能够解决它呢？

Input

第一行包含整数 n (1 ≤ n ≤ 10*5) —数组元素的数量。第二行包含 n 个整数a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n)。

第三行包含唯一的整数 q (1 ≤ q ≤ 10*5) —问题的数量。接下来的q行包含了这些询问。

因为你需要在线回答这些问题，所以这些问题将会被编码。第一种类型的询问将会以以下形式给出： 1 Li Ri  。第二种类型的询问将会以以下形式给出： 2 Li Ri Ki 。所有输入的数字都是整数，它们满足以下条件：1 ≤ Li,Ri,Ki ≤ n.

为解码输入的问题，你需要按以下转换操作：

li = ((Li + lastans - 1) mod n) + 1; 

ri = ((Ri + lastans - 1) mod n) + 1; 

ki=((Ki + lastans - 1) mod n) + 1.

lastans 是到当前询问为止最后一个第二种类型的询问的答案 (初始, lastans = 0)。如果转换后， li 比 ri  大，你需要交换这两个数字。

Output

对于每一个第二种类型的问题以单独一行输出答案。

Input示例

7

6 6 2 7 4 2 5

7

1 3 6

2 2 4 2

2 2 4 7

2 2 2 5

1 2 6

1 1 4

2 1 7 3

Output示例

分块封装队列

安利隔壁sdfzyhx的Splay解法： http://blog.csdn.net/sdfzyhx/article/details/73655923

这个循环操作看上去很麻烦，很难用数据结构直接维护。

考虑分块，每块内维护数列和每个数的出现次数，这样每次循环的时候只需要修改首尾两块。

查询时就暴力统计首尾两块，中间直接查桶即可。

为了防止循环过多导致块严重变形，每次循环的时候把每个中间整块的尾元素移到下一个整块里，这样每块的大小可以保持不变。

因为块内操作有点多，写成了封装形式的，看着异常舒心233

块内用循环队列好像比链表省空间？

(算错了数组大小，RE了三次)

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 const int N=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 struct chain{

     int a[],hd,tl;

     int cnt[mxn];

     void init(){hd=;tl=;return;}

     void add_front(int x){

         hd=hd-;if(hd<)hd=;

         a[hd]=x;

         cnt[x]++;

         return;

     }

     void add_back(int x){

         tl=tl+;if(tl>)tl=;

         a[tl]=x;

         cnt[x]++;

         return;

     }

     void del_front(){

         cnt[a[hd]]--;

         hd=hd+;if(hd>)hd=;

         return;

     }

     void del_back(){

         cnt[a[tl]]--;

         tl=tl-;if(tl<)tl=;

         return;

     }

     void rotate(int l,int r){

 //        printf("rotate:%d %d\n",l,r);

         int st=(hd+l-)%,ed=(hd+r-)%;

 //        printf("st:%d ed:%d\n",st,ed);

         int tmp=a[ed];

         while(ed!=st){

             a[ed]=(ed==)?a[]:a[ed-];

             ed--;if(ed<)ed=;

         }

         a[st]=tmp;

         return;

     }

     int calc(int L,int R,int K){

         int st=(hd+L-)%,ed=(hd+R-)%;

         int res=(a[st]==K);

         while(st^ed){

             st=st+;if(st>)st=;

             res+=(a[st]==K);

         }

         return res;

     }

     int calc_back(int n,int K){

 //        printf("cback:n:%d K:%d\n",n,K);

         int st=tl-n+;

 //        printf("st:%d tl:%d\n",st,tl);

         if(st<)st+=;

         int res=(a[st]==K);

         while(st^tl){

             st=st+;if(st>)st=;

             if(a[st]==K)res++;

         }

         return res;

     }

     int calc_front(int n,int K){

         int ed=(hd+n-)%;

         int st=hd;

         int res=(a[st]==K);

         while(st^ed){

             st=st+;if(st>)st=;

             if(a[st]==K)res++;

         }

         return res;

     }

     int head(){

         return a[hd];

     }

     int tail(){

         return a[tl];

     }

     void debug(){

         printf("debug:\n");

         int x=hd;

         printf("%d ",a[hd]);

         while(x^tl){

             x++;if(x>)x=;

             printf("%d ",a[x]);

         }

         puts("");

         return;

     }

 }c[N];

 int a[mxn];

 int L[N],R[N],sz,block=;

 int bl[mxn];

 int lastans=;

 void solve(){

     int Q=read(),op,ql,qr;

     while(Q--){

 //        printf("Q:%d\n",Q);

         op=read();

         ql=read();ql=(ql+lastans-)%n+;

         qr=read();qr=(qr+lastans-)%n+;

         if(ql>qr)swap(ql,qr);

         if(op==){

             if(bl[ql]==bl[qr]){

                 c[bl[ql]].rotate(ql-L[bl[ql]]+,qr-L[bl[ql]]+);

             }

             else{

                 for(int i=bl[ql]+;i<bl[qr];i++){

                     c[i].add_front(c[i-].tail());

                     c[i-].del_back();

                 }

                 c[bl[qr]].add_front(c[bl[qr]-].tail());

                 c[bl[qr]-].del_back();

                 //

                 c[bl[qr]].rotate(,qr-L[bl[qr]]++);

                 c[bl[ql]].add_back(c[bl[qr]].head());

                 //把最后一个元素转到最前面，再加到最前一块的末尾

                 c[bl[qr]].del_front();

                 c[bl[ql]].rotate(ql-L[bl[ql]]+,R[bl[ql]]-L[bl[ql]]+);

             }

         }

         else{

             int K=read();K=(K+lastans-)%n+;

             if(bl[ql]==bl[qr]){

                 int res=;

                 res=c[bl[ql]].calc(ql-L[bl[ql]]+,qr-L[bl[ql]]+,K);

                 printf("%d\n",res);

                 lastans=res;

                 continue;

             }

             int res=;

             for(int i=bl[ql]+;i<bl[qr];i++){

                 res+=c[i].cnt[K];

             }

 //            c[bl[ql]].debug();

 //            c[bl[qr]].debug();

             res+=c[bl[ql]].calc_back(R[bl[ql]]-ql+,K);

             res+=c[bl[qr]].calc_front(qr-L[bl[qr]]+,K);

             printf("%d\n",res);

             lastans=res;

         }

     }

     return;

 }

 int main(){

     int i,j;

     n=read();

     for(i=;i<=n;i++)a[i]=read();

 //    block=min(n,(int)sqrt(n+0.5)+123);

     block=;

     sz=(n-)/block+;

     for(i=;i<=sz;i++){

         L[i]=R[i-]+;

         R[i]=block*i;

         c[i].init();

     }

     R[sz]=min(R[sz],n);

     for(i=;i<=sz;i++){

         for(j=L[i];j<=R[i];j++){

             c[i].add_back(a[j]);

             bl[j]=i;

         }

     }

     solve();

     return ;

 }

巴特西

51nod1471 小S的兴趣

最新文章

热门文章