D. Serega and Fun

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/455/problem/D

Description

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.

Sample Input

6 6 2 7 4 2 5

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

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.csdn.net/blankcqk/article/details/38468729

写得很清楚

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   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-9const int inf=0x3f3f3f3f;const ll infll = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//**************************************************************************************deque
                   
                    ::iterator it;struct node{ deque
                    
                      q; int num[maxn];};node a[500];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=0;i
                     
                      r)swap(l,r); d1=l/block,d2=r/block; d11=l%block,d22=r%block; if(k==1) { 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

你可能感兴趣的文章