题解 P4130 【[NOI2007]项链工厂】

· · 题解

我去，这题居然没人写ODT？ 虽说ODT跑的确实慢...（最后一个点卡时过，960ms+，所以可能要卡点常吧）

于是贡献一发ODT。

本来想了很久的标记处理（就是顺时针转以及翻转）

后来想不出来，本来想弃坑跳线段树的，然后想了想借(co)鉴(py)一下网上的标记处理不就行了？线段树操作用珂朵莉带一带，秒解。然后又肝了很久珂朵莉。

最后还是肝出来了，就是两个小细节注意一下就好了。其他地方没什么亮点，都是珂朵莉基操。

标记处理以及修改的边界维护全是抄的QvQ

//by Judge
#include<set>
#include<cstdio>
#include<iostream>
#define IT set<node>::iterator
using namespace std;
const int M=2e5+5;
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} inline int cread(){ char c=getchar(); static int x;
    while(!isupper(c)) c=getchar();
    switch(c){
        case 'R': x=1; break;
        case 'F': x=2; break;
        case 'S': x=3; break;
        case 'P': x=4; break;
        case 'C': x=5; break;
    } c=getchar(); if(isupper(c)) x=6; return x;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x,char chr='\n'){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]=chr;
}
inline void cmax(int& a,int b) { if(a<b) a=b; }
struct node { int l,r; mutable int v; //都是基操
    node(int l,int r=-1,int v=0):l(l),r(r),v(v){} node() {}
    bool operator < (const node& b) const { return l<b.l; }
}; set<node> s; IT it,lit,rit; int n,m,mov,rev;
inline IT split(int pos) { //都是基操
    it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos) return it;
    --it; int l=it->l,r=it->r,v=it->v;
    s.erase(it),s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).first;
}
inline void update(int l,int r,int v) { //都是基操
    rit=split(r+1),lit=split(l);
    s.erase(lit,rit),s.insert(node(l,r,v));
}
inline int query(int l,int r) { //人类的本质竟然是____
    int res=0,las=0;
    rit=split(r+1),lit=split(l);
    for(; lit!=rit; las=lit->v,++lit)
        res+=lit->v!=las;
    return res;
}
inline int col(int x) { //这里直接split
    return it=split(x),it->v;
}
inline int chg(int x) { //借(chao)来的
    if(rev) x=n-x+2;
    x-=mov;
    for(; x>n; x-=n);
    for(; x<1; x+=n);
    return x;
}
int main() {
    n=read(),m=read();
    for(int i=1,x; i<=n; ++i)
        x=read(),s.insert(node(i,i,x));
    int op,l,r,k,a,b,ans;
    for(int i=1,m=read(); i<=m; ++i) {
        op=cread();
        if(op==1) {
            k=read();
            mov+=(rev)?(-k):k;
            for(; mov>n; mov-=n);
            for(; mov<0; mov+=n);
        } else if(op==2) rev^=1;
        else if(op==3) {
            l=read(),r=read();
            l=chg(l),r=chg(r);
            a=col(l),b=col(r);
            update(l,l,b);
            update(r,r,a);
        } else if(op==4) {
            l=read(),r=read(),k=read();
            l=chg(l),r=chg(r);
            if(rev) swap(l,r);
            if(l<=r) update(l,r,k);
            else update(l,n,k),update(1,r,k);
        } else if(op==5) {
            ans=query(1,n);
            if(ans>1) ans-=col(1)==col(n); //这里要特判啊
            print(ans);
        } else if(op==6) {
            l=read(),r=read();
            l=chg(l),r=chg(r);
            if(rev) swap(l,r);
            if(l<=r) ans=query(l,r);
            else {
                ans=query(l,n)+query(1,r);
                if(ans>1) ans-=col(1)==col(n); //这里也是
            }
            print(ans);
        }
    } return Ot(),0;
}