题目来源： 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示例
2
1
0
0
分块 封装 队列
安利隔壁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 ;
}