萌新求助,望大佬支援

P4130 [NOI2007] 项链工厂

Los_chase @ 2019-09-10 21:07:33

不知道为什么RE惹。

#include<bits/stdc++.h>
#define LL long long
#define N 500010
using namespace std;

struct NODE{
    int means,lcol,rcol,modi,ls,rs;
}c[N<<2];

int f=1,bg=1,a[N],n,ans,m;

inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

inline int trans(int p){
    return (bg+(p-1)*f+n)%n;
}

inline void push_down(int p){
    if (c[p].modi){
        c[p].lcol=c[p].rcol=c[c[p].ls].modi=c[c[p].ls].modi=c[p].modi;
        if (c[p].ls==0||c[p].rs==0) c[0].modi=0;
        c[p].means=1,c[p].modi=0;
    }
}

inline void push_up(int p){
    if (!p) return;
    push_down(c[p].ls);push_down(c[p].rs);
    c[p].means=c[c[p].ls].means+c[c[p].rs].means;
    if (c[p].means>=1&&c[c[p].ls].rcol==c[c[p].rs].lcol) c[p].means--;
    if (c[p].ls) c[p].lcol=c[c[p].ls].lcol;
    if (c[p].rs) c[p].rcol=c[c[p].rs].rcol;
}

void build(int rt,int l,int r){
    if (l>r) return;
    c[rt].lcol=a[l],c[rt].rcol=a[r],c[rt].ls=c[rt].rs=c[rt].modi=0;
    if (l==r){
        c[rt].means=1;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    if (l<=mid) c[rt].ls=rt<<1;
    if (mid+1<=r) c[rt].rs=rt<<1|1;
    push_up(rt);
}

int getcolor(int rt,int l,int r,int p){
    push_down(rt);
    if (l==p) return c[rt].lcol;
    if (r==p) return c[rt].rcol;
    int mid=(1+r)>>1;
    if (p<=mid) return getcolor(c[rt].ls,l,mid,p);
    return getcolor(c[rt].rs,mid+1,r,p);
}

void paint(int rt,int lx,int rx,int l,int r,int col){
    if (l<=lx&&r>=rx){
        c[rt].modi=col;
        return;
    }
    push_down(rt);
    int mid=(lx+rx)>>1;
    if (l<=mid) paint(c[rt].ls,lx,mid,l,r,col);
    if (r>mid) paint(c[rt].rs,mid+1,rx,l,r,col);
    push_up(rt);
}

int query(int rt,int lx,int rx,int l,int r){
    push_down(rt);
    if (l==lx&&r==rx) return c[rt].means;
    int mid=(lx+rx)>>1,ans=0;
    if (r<=mid) ans=query(c[rt].ls,lx,mid,l,r);
    else{
        if (l>mid) ans=query(c[rt].rs,mid+1,rx,l,r);
        else{
            ans=query(c[rt].ls,lx,mid,l,mid)+query(c[rt].rs,mid+1,rx,mid+1,r);
            if (c[c[rt].ls].rcol==c[c[rt].rs].lcol) ans--;
            if (ans<=0) ans=1;
        }
    }
    return ans;
}

int main(){
    n=read(),ans=read()*0;
    for (int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    m=read();
    while (m--){
        ans=0;
        char opt=getchar(),op1=getchar();
        if (opt=='R') bg+=n+f*read(),bg%=n;
        if (opt=='F') f*=-1;
        if (opt=='S'){
            int x=trans(read()),y=trans(read()),c1=getcolor(1,1,n,y),c2=getcolor(1,1,n,x);
            paint(1,1,n,x,x,c1);
            paint(1,1,n,y,y,c2);
        }
        if (opt=='P'){
            int x=trans(read()),y=trans(read()),col=read();
            if (f==1){
                if (x>y){
                    paint(1,1,n,x,n,col);
                    paint(1,1,n,1,y,col);
                }
                if (x<=y) paint(1,1,n,x,y,col);
            }
            else{
                if (x<y){
                    paint(1,1,n,y,n,col);
                    paint(1,1,n,1,x,col);
                }
                if (x>=y) paint(1,1,n,y,x,col);
            }
        }
        if (opt=='C'&&op1=='S'){
            int x=trans(read()),y=trans(read());
            if (f==1){
                if (x>y){
                    ans+=query(1,1,n,x,n)+query(1,1,n,1,y);
                    if (c[1].lcol==c[1].rcol&&ans>1) ans--;
                }
                if (x<=y) ans=query(1,1,n,x,y);
            }
            else{
                if (x<y){
                    ans+=query(1,1,n,1,x)+query(1,1,n,y,n);
                    if (c[1].lcol==c[1].rcol&&ans>1) ans--;
                }
                if (x>=y) ans=query(1,1,n,y,x);
            }
            printf("%d\n",ans);
        }
        if (opt=='C'&&op1=='\n'){
            ans=c[1].means;
            if (c[1].lcol==c[1].rcol&&ans>1) ans--;
            printf("%d\n",ans);
        }
    }
    return 0;
}

by 雪树蟋蟀 @ 2019-09-10 21:11:22

@czhzh trans(int p) 这里错了


by Los_chase @ 2019-09-10 21:18:30

改了,但还是RE了


|