torque @ 2019-09-30 22:23:52

#include <cstdio>
#include <cstdlib>
#define N 500001
#define rnt register int
using namespace std;
struct Tree{
    int lc,rc,tag,sum;
} t[N*4];
bool R;
char s[101];
int n,m,x,y,k,C,F,d[N];
void build(int id,int l,int r){
    t[id].lc=d[l],t[id].rc=d[r];
    if(l==r){
        t[id].sum=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    t[id].sum=t[id<<1].sum+t[id<<1|1].sum;
    if(t[id<<1].rc==t[id<<1|1].lc) --t[id].sum;
}
inline void FindLoc(int &x,int &y){
    if(!R){
        x=x-1+F;if(x>n) x-=n;
        y=y-1+F;if(y>n) y-=n;
    }
    else{
        x=F-x+1;if(x<1) x+=n;
        y=F-y+1;if(y<1) y+=n;
    }
}
inline void pushdown(int id){
    if(t[id].tag){
        t[id<<1].sum=t[id<<1|1].sum=1;
        t[id<<1].lc=t[id<<1|1].lc=t[id].tag;
        t[id<<1].rc=t[id<<1|1].rc=t[id].tag;
        t[id<<1].tag=t[id<<1|1].tag=t[id].tag;
        t[id].tag=0;
    }
}
int query(int id,int l,int r,int x){
    pushdown(id);
    if(l==x) return t[id].lc;
    if(r==x) return t[id].rc;
    int mid=(l+r)>>1;
    if(x<=mid) return query(id<<1,l,mid,x);
    else return query(id<<1|1,mid+1,r,x);
}
void change(int id,int l,int r,int L,int R,int c){
    pushdown(id);
    if(l==L && r==R){
        t[id].sum=1;
        t[id].lc=t[id].rc=t[id].tag=c;
        return ;
    }
    int mid=(l+r)>>1;
    if(R<=mid) change(id<<1,l,mid,L,R,c);
    else if(L>mid) change(id<<1|1,mid+1,r,L,R,c);
    else{
        change(id<<1,l,mid,L,mid,c);
        change(id<<1|1,mid+1,r,mid+1,R,c);
    }
    t[id].sum=t[id<<1].sum+t[id<<1|1].sum;
    if(t[id<<1].rc==t[id<<1|1].lc) --t[id].sum;
}
int ask(int id,int l,int r,int L,int R){
    pushdown(id);
    if(l==L && r==R) return t[id].sum;
    int mid=(l+r)>>1;
    if(R<=mid) return ask(id<<1,l,mid,L,R);
    else if(L>mid) return ask(id<<1|1,mid+1,r,L,R);
    else{
        int ans=ask(id<<1,l,mid,L,mid)+ask(id<<1|1,mid+1,r,mid+1,R);
        if(t[id<<1].rc==t[id<<1|1].lc) --ans;
        return ans;
    }
}
int main(){
    scanf("%d%d",&n,&C);F=1;
    for(rnt i=1;i<=n;i=-~i) scanf("%d",&d[i]);
    build(1,1,n);scanf("%d",&m);
    for(rnt i=1;i<=m;i=-~i){
        scanf("%s",s);
        switch(s[0]){
            case 'R':{
                scanf("%d",&k);
                F=(F+k-1)%n+1;
                break;
            }
            case 'F':{
                R=!R;
                F=(n+2-F)%n;
                break;
            }
            case 'S':{
                scanf("%d%d",&x,&y);
                FindLoc(x,y);
                int OriCol=query(1,1,n,x);
                change(1,1,n,x,x,query(1,1,n,y));
                change(1,1,n,y,y,OriCol);
                break;
            }
            case 'P':{
                scanf("%d%d%d",&x,&y,&k);
                FindLoc(x,y);
                if(R) x^=y^=x^=y;
                if(y>=x) change(1,1,n,x,y,k);
                else{change(1,1,n,x,n,k);change(1,1,n,1,y,k);}
                break;
            }
            case 'C':{
                if(s[1]=='S'){
                    int ans;
                    scanf("%d%d",&x,&y);
                    FindLoc(x,y);
                    if(R) x^=y^=x^=y;
                    if(y>=x) ans=ask(1,1,n,x,y);
                    else{
                        ans=ask(1,1,n,x,n)+ask(1,1,n,1,y);
                        if(t[1].lc==t[1].rc) --ans;
                    }
                    printf("%d\n",ans);
                }
                else printf("%d\n",t[1].sum+((t[1].lc==t[1].rc)?(-1):0));
                break;
            }
        }
    }
    return 0;
}

by TOGEKISS @ 2019-10-10 18:18:44

include <cstdio>

include <algorithm>

include <cstdlib>

include <cstring>

using namespace std; int const N=500010; struct segment_tree{ int lch,rch; int l,r; int lcr,rcr; int sum; int idx; }tree[N*2+1000]; int n,m,q,d[N],tot,root,top,fp; char ch[4]; void push_up(int root) { int lc=tree[root].lch; int rc=tree[root].rch; tree[root].sum=tree[lc].sum+tree[rc].sum; if(tree[lc].rcr==tree[rc].lcr) tree[root].sum--; tree[root].lcr=tree[lc].lcr; tree[root].rcr=tree[rc].rcr; } void create_tree(int &root,int left,int right) { root=tot++; // root=++tot; tree[root].lch=tree[root].rch=-1; if(left==right) { tree[root].l=tree[root].r=left; tree[root].sum=1; tree[root].idx=tree[root].lcr=tree[root].rcr=d[left]; } else { int mid=(left+right)/2; tree[root].l=left; tree[root].r=right; create_tree(tree[root].lch,left,mid); create_tree(tree[root].rch,mid+1,right); push_up(root); } } void push_down(int root) { if(tree[root].idx!=0) { int lc=tree[root].lch; int rc=tree[root].rch; tree[lc].lcr=tree[root].idx; tree[lc].rcr=tree[root].idx; tree[rc].rcr=tree[root].idx; tree[rc].lcr=tree[root].idx; tree[lc].idx=tree[root].idx; tree[rc].idx=tree[root].idx; tree[lc].sum=tree[rc].sum=1; tree[root].idx=0; } } void update(int root,int left,int right,int val) { if(left<=tree[root].l&&tree[root].r<=right) { tree[root].lcr=tree[root].rcr=val; tree[root].sum=1; tree[root].idx=val; return ; } else { push_down(root); int mid=(tree[root].l+tree[root].r)/2; if(right<=mid) update(tree[root].lch,left,right,val); else if(left>mid) update(tree[root].rch,left,right,val); else { update(tree[root].lch,left,mid,val); update(tree[root].rch,mid+1,right,val); } push_up(root); } } int query_point(int root,int pos) { if(tree[root].l==tree[root].r) return tree[root].lcr; else { push_down(root); int mid=(tree[root].l+tree[root].r)/2; if(pos<=mid) return query_point(tree[root].lch,pos); else return query_point(tree[root].rch,pos); } } int get_pos(int pos) { if(fp) pos=n-pos+2; pos-=top; while(pos<=0) pos+=n; while(pos>n) pos-=n; return pos; } void flip() { fp^=1; } void ncswap(int a,int b) { int t1=get_pos(a); int t2=get_pos(b); int col1=query_point(root,t1); int col2=query_point(root,t2); update(root,t1,t1,col2); update(root,t2,t2,col1); } void paint(int a,int b,int val) { int t1=get_pos(a); int t2=get_pos(b); if(fp) swap(t1,t2); if(t1<=t2) update(root,t1,t2,val); else { update(root,t1,n,val); update(root,1,t2,val); } } int count() { int ans=tree[root].sum; int col1=query_point(root,n); int col2=query_point(root,1); if(col1==col2) ans--; if(ans<1) ans=1; return ans; } int query(int root,int left,int right) { if(left<=tree[root].l&&tree[root].r<=right) { return tree[root].sum; } else { push_down(root); int mid=(tree[root].l+tree[root].r)/2; if(right<=mid) return query(tree[root].lch,left,right); else if(left>mid) return query(tree[root].rch,left,right); else { int a=query(tree[root].lch,left,mid); int b=query(tree[root].rch,mid+1,right); int ans=a+b; if(tree[tree[root].lch].rcr==tree[tree[root].rch].lcr) ans--; return ans; } } } int cs(int a,int b) { int t1=get_pos(a); int t2=get_pos(b); if(fp) swap(t1,t2); if(t1<=t2) return query(root,t1,t2); else { int ans=query(root,t1,n)+query(root,1,t2); int col1=query_point(root,n); int col2=query_point(root,1); if(col1==col2) ans--; return ans; } } int main () { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); create_tree(root,1,n); scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%s",ch); if(ch[0]=='R') { int k; scanf("%d",&k); if(fp) top-=k; else top+=k; while(top>n) top-=n; while(top<=0) top+=n; } if(ch[0]=='F') flip(); if(ch[0]=='S') { int a,b; scanf("%d%d",&a,&b); ncswap(a,b); } if(ch[0]=='P') { int a,b,c; scanf("%d%d%d",&a,&b,&c); paint(a,b,c); } if(ch[0]=='C'&&ch[1]!='S') printf("%d\n",count()); if(ch[0]=='C'&&ch[1]=='S') { int a,b; scanf("%d%d",&a,&b); printf("%d\n",cs(a,b)); } } return 0; }

by TOGEKISS @ 2019-10-10 18:19:20

不希望更丰富的展现？使用XETAL