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?
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'ir'i. A query of the second type will be given in format: 2 l'ir'ik'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
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
2
1
0
0
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
2
0
分块+双端队列
每次更新对每块进行操作：
1.中间的整块：取出最后一个放入下一块的前端；
2.两端的块：左边的块放入给定右边界位置的数字，右端的块删除给定右边界位置的数字
每次询问：
中间的整块直接查询，两边的块遍历可访问的位置；
#include <cstdio>
#include <stack>
#include <cmath>
#include <queue>
#include <string>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm> #define lid id<<1
#define rid id<<1|1
#define closein cin.tie(0)
#define scac(a) scanf("%c",&a)
#define scad(a) scanf("%d",&a)
#define print(a) printf("%d\n",a)
#define debug printf("hello world")
#define form(i,n,m) for(int i=n;i<m;i++)
#define mfor(i,n,m) for(int i=n;i>m;i--)
#define nfor(i,n,m) for(int i=n;i>=m;i--)
#define forn(i,n,m) for(int i=n;i<=m;i++)
#define scadd(a,b) scanf("%d%d",&a,&b)
#define memset0(a) memset(a,0,sizeof(a))
#define scaddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scadddd(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d) #define INF 0x3f3f3f3f
#define maxn 100005
typedef long long ll;
using namespace std;
//---------AC(^-^)AC---------\\ deque<int>::iterator it;
struct node
{
deque<int> q;
int num[maxn];
}block[];
int n, m, blo, ans;
int pos[maxn]; void update(int a, int b)
{
if (pos[a] == pos[b])
{
it = block[pos[b]].q.begin() + ((b-)%blo);
int tmp = *it;
block[pos[b]].q.erase(block[pos[b]].q.begin() + ((b-)%blo));
block[pos[b]].q.insert(block[pos[a]].q.begin() + ((a-)%blo), tmp);
}
else
{
it = block[pos[b]].q.begin() + ((b-)%blo);
int tmp = *it;
block[pos[b]].num[tmp]--;
block[pos[b]].q.erase(block[pos[b]].q.begin() + ((b-)%blo));
for (int i = pos[a]; i < pos[b]; i++) {
int x = block[i].q.back();
block[i].q.pop_back();
block[i].num[x]--;
block[i + ].q.push_front(x);
block[i + ].num[x]++;
}
block[pos[a]].q.insert(block[pos[a]].q.begin() + ((a-)%blo), tmp);
block[pos[a]].num[tmp]++;
}
}
void query(int a, int b, int c)
{
ans=;
if (pos[a] == pos[b])
{
for (it = block[pos[a]].q.begin() + ((a-)%blo); it <= block[pos[a]].q.begin() + ((b-)%blo); it++)
if ((*it) == c) ans++;
}
else {
for (int i = pos[a] + ; i < pos[b]; i++) ans += block[i].num[c];
for (it = block[pos[a]].q.begin() + ((a-)%blo); it < block[pos[a]].q.end(); it++)
if ((*it) == c) ans++;
for (it = block[pos[b]].q.begin(); it <= block[pos[b]].q.begin() + ((b-)%blo); it++)
if ((*it) == c) ans++;
}
printf("%d\n", ans);
} int main()
{
scad(n);
blo = sqrt(n);
if (n%blo) blo++;
forn(i, , n) pos[i] = (i - )/blo + ; forn(i, , n) {
int x;
scad(x);
int s = pos[i];
block[s].q.push_back(x);
block[s].num[x]++;
}
scad(m);
ans = ;
while (m--)
{
int op;
scad(op);
if (op == )
{
int l, r;
scadd(l, r);
l = (l + ans - ) % n+;
r = (r + ans - ) % n+;
if (l > r) swap(l, r);
update(l, r);
}
else
{
int l, r, k;
scaddd(l, r, k);
l = (l + ans - ) % n + ;
r = (r + ans - ) % n + ;
k = (k + ans - ) % n + ;
if (l > r) swap(l, r);
query(l, r, k);
}
}
return ;
}