http://codeforces.com/contest/455/problem/D
Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.
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.
Examples
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
Input
8
8 4 2 2 7 7 8 8
8
1 8 8
2 8 1 7
1 8 1
1 7 3
2 8 8 3
1 1 4
1 2 7
1 4 5
Output
2
0 先来TLE
#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N=100000+100;
inline void scan_d(int &ret) {
char c; ret=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
int n,q,sq,a[N],bl[N],op,L[400],R[400],tot;
int last,s[400][N];
vector<int>b[400];
inline void updata(int l ,int r ){
int x=bl[l],y=bl[r];
int v=*(b[x].end()-1),pre=v;//记录首块的最后一项
int en=b[y][r-L[y]];//记录要操作的区间的最后一项
if(x==y){
b[x].erase(b[y].begin()+r-L[y]);//删除最后一项
b[x].insert(b[x].begin()+l-L[x],en);//插入最后一项到区间左边
}else{
--s[x][v];//增减块内包含数的个数
++s[x][en];
b[x].erase(b[x].end()-1);//删除区间最后一项
b[x].insert(b[x].begin()+l-L[x],en);//插入最后一项到区间左边
for (int i=x+1;i<=y-1;++i){
--s[i][*(b[i].end()-1)];
++s[i][pre];
int pp=b[i][b[i].size()-1];//记录本块的最后一项
b[i].erase(b[i].end()-1);//删除块最后一项
b[i].insert(b[i].begin(),pre);//插入上一块最后一项到本块左边
pre=pp;
}
--s[y][en];
++s[y][pre];
b[y].erase(b[y].begin()+r-L[y]);//删除区间最后一项
b[y].insert(b[y].begin(),pre);//插入上一块最后一项到本块左边
}
}
inline int query(int l,int r,int k){
int ans=0;
int x=bl[l],y=bl[r];
if (x==y) {
for (int i=l;i<=r;++i)
ans+=(b[x][i-L[x]]==k);
return ans;
}
for (int i=l;i<=R[x];++i)
ans+=(b[x][i-L[x]]==k);//朴素求区间两端的块内的k个数
for (int i=L[y];i<=r;++i)
ans+=(b[y][i-L[y]]==k);
for (int i=x+1;i<=y-1;++i)
ans+=s[i][k];//中间块查询s数组
return ans;
}
int main()
{
//scanf("%d",&n);
scan_d(n);
sq=sqrt(n);
tot=n/sq;
if(n%sq)tot++;
for(int i=1;i<=tot;i++){
L[i]=(i-1)*sq+1;
R[i]=i*sq;
}
R[tot]=n;
for(int i=1;i<=n;i++){
bl[i]=(i-1)/sq+1;
//scanf("%d",&a[i]);
scan_d(a[i]);
s[bl[i]][a[i]]++;
b[bl[i]].push_back(a[i]);
}
//scanf("%d",&q);
scan_d(q);
int li,ri,ki;
int l,r,k;
while(q--){
//scanf("%d%d%d",&op,&li,&ri);
scan_d(op);
scan_d(li);
scan_d(ri);
l=(li+last-1)%n+1;
r=(ri+last-1)%n+1;
if(l>r)
swap(l,r);
if(op==1){
updata(l,r);
}else{
//scanf("%d",&ki);
scan_d(ki);
k=(ki+last-1)%n+1;
last=query(l,r,k);
printf("%d\n",last);
}
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本一
分块+双端队列
#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N=100000+100;
inline void scan_d(int &ret) {
char c; ret=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
int n,q,sq,a[N],bl[N],op,L[400],R[400],tot;
int last,s[400][N];
deque<int>b[400];
inline void updata(int l ,int r ){
int x=bl[l],y=bl[r];
if(x==y){
int temp=b[x][r-L[x]];
for(int i=r; i>l; i--){
b[x][i-L[x]]=b[x][i-1-L[x]];
}
b[x][l-L[x]]=temp;
return ;
}
int temp=b[y][r-L[y]];
int temp2=b[x][R[x]-L[x]];
s[x][temp2]--;
s[y][temp]--;
for(int i=R[x]; i>l; i--){
b[x][i-L[x]]=b[x][i-L[x]-1];
}
b[x][l-L[x]]=temp;
s[x][temp]++;
for(int i=x+1; i<y; i++){
int tp=temp2;
s[i][temp2]++;
temp2=b[i][R[i]-L[i]];
b[i].pop_back();
b[i].push_front(tp);
s[i][temp2]--;
}
for(int i=r; i>L[y]; i--){
b[y][i-L[y]]=b[y][i-L[y]-1];
}
b[y][0]=temp2;
s[y][temp2]++;
}
inline int query(int l,int r,int k){
int ans=0;
int x=bl[l],y=bl[r];
if (x==y) {
for (int i=l;i<=r;++i)
ans+=(b[x][i-L[x]]==k);
return ans;
}
for (int i=l;i<=R[x];++i)
ans+=(b[x][i-L[x]]==k);//朴素求区间两端的块内的k个数
for (int i=L[y];i<=r;++i)
ans+=(b[y][i-L[y]]==k);
for (int i=x+1;i<=y-1;++i)
ans+=s[i][k];//中间块查询s数组
return ans;
}
int main()
{
//scanf("%d",&n);
scan_d(n);
sq=sqrt(n);
tot=n/sq;
if(n%sq)tot++;
for(int i=1;i<=tot;i++){
L[i]=(i-1)*sq+1;
R[i]=i*sq;
}
R[tot]=n;
for(int i=1;i<=n;i++){
bl[i]=(i-1)/sq+1;
//scanf("%d",&a[i]);
scan_d(a[i]);
s[bl[i]][a[i]]++;
b[bl[i]].push_back(a[i]);
}
//scanf("%d",&q);
scan_d(q);
int li,ri,ki;
int l,r,k;
while(q--){
//scanf("%d%d%d",&op,&li,&ri);
scan_d(op);
scan_d(li);
scan_d(ri);
l=(li+last-1)%n+1;
r=(ri+last-1)%n+1;
if(l>r)
swap(l,r);
if(op==1){
updata(l,r);
}else{
//scanf("%d",&ki);
scan_d(ki);
k=(ki+last-1)%n+1;
last=query(l,r,k);
printf("%d\n",last);
}
}
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号