首页 > 代码库 > 51nod1471 小S的兴趣
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示例
76 6 2 7 4 2 571 3 62 2 4 22 2 4 72 2 2 51 2 61 1 42 1 7 3Output示例
2100
分块 封装 队列
安利隔壁sdfzyhx的Splay解法： http://blog.csdn.net/sdfzyhx/article/details/73655923
这个循环操作看上去很麻烦，很难用数据结构直接维护。
考虑分块，每块内维护数列和每个数的出现次数，这样每次循环的时候只需要修改首尾两块。
查询时就暴力统计首尾两块，中间直接查桶即可。
为了防止循环过多导致块严重变形，每次循环的时候把每个中间整块的尾元素移到下一个整块里，这样每块的大小可以保持不变。
因为块内操作有点多，写成了封装形式的，看着异常舒心233
块内用循环队列好像比链表省空间？
(算错了数组大小，RE了三次)
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=100005; 8 const int N=298; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 int n; 16 struct chain{ 17 int a[503],hd,tl; 18 int cnt[mxn]; 19 void init(){hd=1;tl=0;return;} 20 void add_front(int x){ 21 hd=hd-1;if(hd<0)hd=500; 22 a[hd]=x; 23 cnt[x]++; 24 return; 25 } 26 void add_back(int x){ 27 tl=tl+1;if(tl>500)tl=0; 28 a[tl]=x; 29 cnt[x]++; 30 return; 31 } 32 void del_front(){ 33 cnt[a[hd]]--; 34 hd=hd+1;if(hd>500)hd=0; 35 return; 36 } 37 void del_back(){ 38 cnt[a[tl]]--; 39 tl=tl-1;if(tl<0)tl=500; 40 return; 41 } 42 void rotate(int l,int r){ 43 // printf("rotate:%d %d\n",l,r); 44 int st=(hd+l-1)%501,ed=(hd+r-1)%501; 45 // printf("st:%d ed:%d\n",st,ed); 46 int tmp=a[ed]; 47 while(ed!=st){ 48 a[ed]=(ed==0)?a[500]:a[ed-1]; 49 ed--;if(ed<0)ed=500; 50 } 51 a[st]=tmp; 52 return; 53 } 54 int calc(int L,int R,int K){ 55 int st=(hd+L-1)%501,ed=(hd+R-1)%501; 56 int res=(a[st]==K); 57 while(st^ed){ 58 st=st+1;if(st>500)st=0; 59 res+=(a[st]==K); 60 } 61 return res; 62 } 63 int calc_back(int n,int K){ 64 // printf("cback:n:%d K:%d\n",n,K); 65 int st=tl-n+1; 66 // printf("st:%d tl:%d\n",st,tl); 67 if(st<0)st+=501; 68 int res=(a[st]==K); 69 while(st^tl){ 70 st=st+1;if(st>500)st=0; 71 if(a[st]==K)res++; 72 } 73 return res; 74 } 75 int calc_front(int n,int K){ 76 int ed=(hd+n-1)%501; 77 int st=hd; 78 int res=(a[st]==K); 79 while(st^ed){ 80 st=st+1;if(st>500)st=0; 81 if(a[st]==K)res++; 82 } 83 return res; 84 } 85 int head(){ 86 return a[hd]; 87 } 88 int tail(){ 89 return a[tl]; 90 } 91 void debug(){ 92 printf("debug:\n"); 93 int x=hd; 94 printf("%d ",a[hd]); 95 while(x^tl){ 96 x++;if(x>500)x=0; 97 printf("%d ",a[x]); 98 } 99 puts("");100 return;101 }102 }c[N];103 int a[mxn];104 int L[N],R[N],sz,block=0;105 int bl[mxn];106 int lastans=0;107 void solve(){108 int Q=read(),op,ql,qr;109 while(Q--){110 // printf("Q:%d\n",Q);111 op=read();112 ql=read();ql=(ql+lastans-1)%n+1;113 qr=read();qr=(qr+lastans-1)%n+1;114 if(ql>qr)swap(ql,qr);115 if(op==1){116 if(bl[ql]==bl[qr]){117 c[bl[ql]].rotate(ql-L[bl[ql]]+1,qr-L[bl[ql]]+1);118 }119 else{120 for(int i=bl[ql]+1;i<bl[qr];i++){121 c[i].add_front(c[i-1].tail());122 c[i-1].del_back();123 }124 c[bl[qr]].add_front(c[bl[qr]-1].tail());125 c[bl[qr]-1].del_back();126 //127 c[bl[qr]].rotate(1,qr-L[bl[qr]]+1+1);128 c[bl[ql]].add_back(c[bl[qr]].head()); 129 //把最后一个元素转到最前面，再加到最前一块的末尾130 c[bl[qr]].del_front();131 c[bl[ql]].rotate(ql-L[bl[ql]]+1,R[bl[ql]]-L[bl[ql]]+1);132 }133 }134 else{135 int K=read();K=(K+lastans-1)%n+1;136 if(bl[ql]==bl[qr]){137 int res=0;138 res=c[bl[ql]].calc(ql-L[bl[ql]]+1,qr-L[bl[ql]]+1,K);139 printf("%d\n",res);140 lastans=res;141 continue;142 }143 int res=0;144 for(int i=bl[ql]+1;i<bl[qr];i++){145 res+=c[i].cnt[K];146 }147 // c[bl[ql]].debug();148 // c[bl[qr]].debug();149 res+=c[bl[ql]].calc_back(R[bl[ql]]-ql+1,K);150 res+=c[bl[qr]].calc_front(qr-L[bl[qr]]+1,K);151 printf("%d\n",res);152 lastans=res;153 }154 }155 return;156 }157 int main(){158 int i,j;159 n=read();160 for(i=1;i<=n;i++)a[i]=read();161 // block=min(n,(int)sqrt(n+0.5)+123);162 block=400;163 sz=(n-1)/block+1;164 for(i=1;i<=sz;i++){165 L[i]=R[i-1]+1;166 R[i]=block*i;167 c[i].init();168 }169 R[sz]=min(R[sz],n);170 for(i=1;i<=sz;i++){171 for(j=L[i];j<=R[i];j++){172 c[i].add_back(a[j]);173 bl[j]=i;174 }175 }176 solve();177 return 0;178 }
51nod1471 小S的兴趣
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。