D. Serega and Fun
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/455/problem/D
Description
You are given an array a consisting of n positive integers and queries to it. The queries can be of two types:
Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner:
a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].
Count how many numbers equal to k are on the segment from l to r (both borders inclusive).
Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it?
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of the array. The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).
The third line contains a single integer q (1 ≤ q ≤ 105) — the number of queries. The next q lines contain the queries.
As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: 1 l'i r'i. A query of the second type will be given in format: 2 l'i r'i k'i. All the number in input are integer. They satisfy the constraints: 1 ≤ l'i, r'i, k'i ≤ n.
To decode the queries from the data given in input, you need to perform the following transformations:
li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.
Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0). If after transformation li is greater than ri, you must swap these values.
Output
For each query of the 2-nd type print the answer on a single line.
Sample 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
Sample Output
2
1
0
0
HINT
题意
2个操作
1.把a[l],a[l+1]……,a[r]变成 a[r],a[l],a[l+1]……,a[r-1]
2.l,r中等于v的数有多少
要求强制在线
题解：
分块，树套树
还是分块吧，用一个deque
我的代码tle 55……
还是看这个人的代码吧：http://blog.****.net/blankcqk/article/details/38468729
写得很清楚
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 100005
#define mod 10007
#define eps 1e-9
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** deque<int>::iterator it;
struct node
{
deque<int> q;
int num[maxn];
};
node a[];
int block,p,q;
int n,l,r,ans,k,d1,d11,d2,d22,tmp,v;
int main()
{
//test;
n=read();
block=int(sqrt(n));
for(int i=;i<n;i++)
{
int x=read();
p=i/block;
a[p].q.push_back(x);
a[p].num[x]++;
}
q=read();
for(int i=;i<q;i++)
{
k=read(),l=read(),r=read();
l=((l+ans-+n)%n);
r=((r+ans-+n)%n);
if(l>r)swap(l,r);
d1=l/block,d2=r/block;
d11=l%block,d22=r%block;
if(k==)
{
if(d1==d2)
{
it=a[d1].q.begin()+d22;
tmp=*it;
a[d1].q.erase(a[d1].q.begin()+d22);
a[d1].q.insert(a[d1].q.begin()+d11,tmp);
}
else
{
it=a[d2].q.begin()+d22;
tmp=*it;
a[d2].q.erase(a[d2].q.begin()+d22);
a[d2].num[tmp]--;
for(int i=d1;i<d2;i++)
{
int x=a[i].q.back();
a[i].q.pop_back();
a[i].num[x]--;
a[i+].q.push_front(x);
a[i+].num[x]++;
}
a[d1].q.insert(a[d1].q.begin()+d11,tmp);
a[d1].num[tmp]++;
}
}
else
{
v=read();
v=((v+ans-)%n)+;
ans=;
if(d1==d2)
{
for(it=a[d1].q.begin()+d11;it<=a[d1].q.begin()+d22;it++)
if(*it==v)
ans++;
}
else
{
for(int i=d1+;i<d2;i++)
ans+=a[i].num[v];
for(it=a[d1].q.begin()+d11;it<a[d1].q.end();it++)
if(*it==v)
ans++;
for(it=a[d2].q.begin();it<=a[d2].q.begin()+d22;it++)
if(*it==v)
ans++;
}
printf("%d\n",ans);
}
}
return ;
}