51nod 1471 小S的兴趣 sqrt

小S喜欢有趣的事。但是，每个人的兴趣都是独特的。小S热衷于自问自答。有一天，小S想出了一个问题。

有一个包含n个正整数的数组a和针对这个数组的几个问题。这些问题有两种类型：

1.      在数组下标l到r的部分上，将一个单元格循环移动到右端。即以下面方式重新分配数组上的元素。

a[l], a[l+1], ..., a[r-1], a[r] → a[r], a[l], a[l+1], ..., a[r-1].

2.      在数组下标l到r的部分上，计算有多少元素的值与k相等。

小S很喜欢这个问题并且很快解决了它，你是否能够解决它呢？

分块，每一个块维护一个链表，也可以用数组模拟，不包含整个区间就暴力更改。

O（nsqrt(n)）

右移相当于在末尾删除一个元素，在首部添加一个元素。

debug了很久，原因：在解密l,r,k，后，有可能l > r,这个时候要swap(l,r)

代码：

  //File Name: nod1471.cpp

  //Author: long

  //Mail: [email protected]

  //Created Time: 2016年09月15日 星期四 21时17分30秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <map>

#define LL long long

using namespace std;

const int MAXN =  + ;

const int NUM = ;

int l[MAXN/NUM+],r[MAXN/NUM+],belong[MAXN];

int a[MAXN],tmp[NUM],cnt;

struct Block{

    int b[NUM],s[MAXN],head,tot;

    void build(const int l,const int r){

        tot = head = ;

        memset(s,,sizeof s);

        for(int i=l;i<=r;i++){

            b[tot++] = a[i];

            s[a[i]]++;

        }

    }

    void right(int st){

        head--;

        if(head < ) head = tot - ;

        cnt = b[head];

        s[cnt]--;

        b[head] = st;

        s[st]++;

    }

    void reset(){

        if(head == ) return ;

        for(int i=;i<tot;i++) tmp[i] = b[i];

        int u = ;

        for(int i=head;i<tot;i++) b[u++] = tmp[i];

        for(int i=;i<head;i++) b[u++] = tmp[i];

        head = ;

    }

    void brute(int st,int l,int r){

        reset();

        cnt = b[r];

        s[cnt]--;

        for(int i=r;i>l;i--) b[i] = b[i-];

        b[l] = st;

        s[st]++;

    }

    int get(int k){

        k = (head + k) % tot;

        return b[k];

    }

    int query(int k){

        return s[k];

    }

    int cal(int l,int r,int k){

        reset();

        int res = ;

        for(int i=l;i<=r;i++)

            if(b[i] == k) res++;

        return res;

    }

}block[MAXN / NUM + ];

void solve(int n){

    for(int i=;i<=n;i++)

        belong[i] = (i - ) / NUM;

    int tot = belong[n] + ,u=;

    for(int i=;i<tot;i++,u+=NUM){

        l[i] = u;

        r[i] = min(u + NUM - ,n);

    }

    for(int i=;i<tot;i++)

        block[i].build(l[i],r[i]);

    int ans = ,q,op,x,y,k;

    scanf("%d",&q);

    while(q--){

        scanf("%d %d %d",&op,&x,&y);

        if(op == ){

            x = (x + ans - ) % n + ;

            y = (y + ans - ) % n + ;

            if(x > y) swap(x,y);

            int bx = belong[x],by = belong[y];

            if(bx == by){

                cnt = block[bx].get(y-l[bx]);

                block[bx].brute(cnt,x-l[bx],y-l[bx]);

            }

            else{

                cnt = block[by].get(y-l[by]);

                block[bx].brute(cnt,x-l[bx],r[bx]-l[bx]);

                for(int i=bx+;i<by;i++)

                    block[i].right(cnt);

                block[by].brute(cnt,,y-l[by]);

            }

        }

        else{

            scanf("%d",&k);

            x = (x + ans - ) % n + ;

            y = (y + ans - ) % n + ;

            k = (k + ans - ) % n + ;

            if(x > y) swap(x,y);

            //cout << x << " " << y << " " << k << " " << endl;

            int bx = belong[x],by = belong[y];

            ans = ;

            if(bx == by)

                ans = block[bx].cal(x-l[bx],y-l[bx],k);

            else{

                ans += block[bx].cal(x-l[bx],r[bx]-l[bx],k);

                for(int i=bx+;i<by;i++)

                    ans += block[i].query(k);

                ans += block[by].cal(,y-l[by],k);

            }

            printf("%d\n",ans);

        }

    }

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        for(int i=;i<=n;i++) scanf("%d",a + i);

        solve(n);

    }

    return ;

}