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了