[CF 455D] Serega and Fun

作法：

通常這種時限比較長而且操作很奇怪的題目都可以考慮根號作法。考慮把整段序列切成$\sqrt{n}$塊，再根據題目的要求決定每塊中要維護的資料結構是什麼。當要把某段區間循環右移時，把他拆成已經切好的幾小塊，就可以得到每個小塊中所必須支援的操作為「將這塊中的某個區間整個右移（因此最右邊的數會消失），並且在左邊補上$x$」。並且大部分的情形右移的區間都是整個塊，因此可以考慮當操作的區間不是整塊的時候暴力重建這個資料結構即可，也就是我們只需要快速的支援「將整塊往右移並在左邊補上$x$」這個操作。至於詢問也是拆成好幾個小塊，對於詢問區間不完全是整塊的部份暴力掃過去就可以了，因此我們需要在一塊中詢問某個數出現了幾次，所以只要在這塊中用一個陣列$cnt$紀錄所有數字出現的次數就可以了。當把整塊中的數都右移時，我們會需要知道此時這塊中的最後一個數是多少，才能維護好$cnt$陣列，也就是會需要查詢某塊中的第$k$個數是誰，並且支援右移操作。這可以用一個環狀的結構來維護，具體來說是一個陣列$a$和一個起點值$st$，代表從$a[st]$開始往後走$i$步就是代表這塊中的第$i$個數是誰（以下記這塊的長度為$sz$），也就是當我們想知道這塊中的第$i$個數時，要查詢的是$a[(st+i)\% sz]$的值。這樣就可以輕鬆維護循環右移操作了，只要把$st$值減一再維護好$cnt$陣列就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 , maxsq=350 ;
 
struct P
{
    int l,r,cnt[maxn],st,sz ;
    int a[2*maxsq] ;
    void build()
    {
        sz=r-l+1 ; st=0 ;
        memset(cnt,0,sizeof(cnt)) ;
        for(int i=0;i<sz;i++) cnt[a[i]]++ ;
    }
    inline int get(int x){return a[(x+st)%sz] ;}
    void shift(int L,int R,int x)
    {
        cnt[a[(R-l+st)%sz]]-- ; cnt[x]++ ;
        if(l==L && r==R)
            st=(st==0?sz-1:st-1) , a[st]=x ;
        else
        {
            L-=l ; R-=l ;
            for(int i=R;i>L;i--) a[(i+st)%sz]=a[(i-1+st)%sz] ;
            a[(L+st)%sz]=x ;
        }
    }
    int query(int L,int R,int x)
    {
        if(l==L && r==R) return cnt[x] ;
        int ret=0 ;
        L-=l ; R-=l ;
        for(int i=L;i<=R;i++) if(a[(i+st)%sz]==x)
            ret++ ;
        return ret ;
    }
}p[maxsq];
 
main()
{
    int n ; scanf("%d",&n) ;
    int sq=2*int(sqrt(n+0.5))+1 ;
    for(int i=0;i<n;i+=sq)
        p[i/sq].l=i , p[i/sq].r=min(i+sq-1,n-1) ;
    for(int i=0;i<n;i++)
    {
        int x ; scanf("%d",&x) ;
        p[i/sq].a[i-i/sq*sq]=x ;
    }
    for(int i=0;i<n;i+=sq)
        p[i/sq].build() ;
    int Q , last=0 ; scanf("%d",&Q) ;
    while(Q--)
    {
        int t,l,r,k ; scanf("%d%d%d",&t,&l,&r) ;
        l=(l+last-1)%n ; r=(r+last-1)%n ;
        if(l>r) swap(l,r) ;
        if(t==1)
        {
            int lg=l/sq , rg=r/sq ;
            int rval=p[rg].get(r-rg*sq) ;
            for(int i=lg;i<=rg;i++)
            {
                int pos=min(r,i*sq+sq-1) ;
                int nval=p[i].get(pos-i*sq) ;
                p[i].shift(max(i*sq,l),pos,rval) ;
                rval=nval ;
            }
        }
        else
        {
            scanf("%d",&k) ; k=(k+last-1)%n+1 ;
            int lg=l/sq , rg=r/sq , ans=0 ;
            for(int i=lg;i<=rg;i++)
                ans+=p[i].query(max(i*sq,l),min(i*sq+sq-1,r),k) ;
            printf("%d\n",last=ans) ;
        }
    }
}