CF455D Sol

一只绝帆 · 2023-08-08 17:16:48 · 题解

一直 RE on #9 的人注意一下，对 std::deque 的迭代器进行数值运算时（例如 it+a-b）可能越界，需要改写成 it+(a-b)。

考虑分块。

每个块开一个 deque，然后操作相当于边界块插入一个元素删除一个元素，中间块左边右边动一个元素。

比块状链表好写多了。

Code:

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define gc getchar
#define l(x) ((x-1)*B+1)
#define r(x) min(n,l(x+1)-1)
#define id(x) ((x-1)/B+1)
using namespace std;
int read() {
    int s=0,w=0;char c=gc();
    while(c<'0'||c>'9') w|=(c=='-'),c=gc();
    while(c>='0'&&c<='9') s=s*10+(c&15),c=gc();
    return w?-s:s;
}
const int N=1e5+5,B=350;
int n,a[N],la,l,r,k,bn[B][N];
deque<int> q[B],tmpl,tmpr;
int main() {
    n=read();
    F(i,1,n) a[i]=read();
    F(i,1,id(n)) F(j,l(i),r(i)) q[i].push_back(a[j]),bn[i][a[j]]++;
    F(QAQ,1,read()) {
        if(read()==1) {
            int l=(read()+la-1)%n+1,r=(read()+la-1)%n+1;
            if(l>r) swap(l,r);
            if(id(l)==id(r)) {
                int p=id(l),tmp=q[p][r-l(p)];
                q[p].erase(q[p].begin()+(r-l(p)));
                q[p].insert(q[p].begin()+(l-l(p)),tmp);
                continue;
            }
            int tmp=q[id(r)][r-l(id(r))];
            bn[id(l)][tmp]++,bn[id(r)][tmp]--;
            q[id(r)].erase(q[id(r)].begin()+(r-l(id(r))));
            q[id(l)].insert(q[id(l)].begin()+(l-l(id(l))),tmp);
            F(i,id(l),id(r)-1) {
                tmp=*(q[i].rbegin());
                bn[i][tmp]--;bn[i+1][tmp]++;
                q[i].pop_back();q[i+1].push_front(tmp);
            }
        } else {
            l=(read()+la-1)%n+1;r=(read()+la-1)%n+1;k=(read()+la-1)%n+1;
            if(l>r) swap(l,r);
            int res=0;
            if(id(l)==id(r)) {
                F(i,l-l(id(l)),r-l(id(l))) res+=(*(q[id(l)].begin()+i)==k);
                cout<<(la=res)<<'\n';
                continue;
            }
            F(i,l-l(id(l)),r(id(l))-l(id(l))) res+=(*(q[id(l)].begin()+i)==k);
            F(i,0,r-l(id(r))) res+=(*(q[id(r)].begin()+i)==k);
            F(i,id(l)+1,id(r)-1) res+=bn[i][k];
            cout<<(la=res)<<'\n';
        }
    }
    return 0;
}