1493: [NOI2007]项链工厂

时间:2021-01-03 00:56:20

线段树。

真还就是个线段树。。

除去操作1,2的话,线段树很容易就处理了,问题在于如何处理操作1和2。(这点没想到)。。

我们用一个delta维护操作1,如果没有旋转就+k,不然就-k。

每次读入i和j的时候用trans处理一下,就成功在O(1)的时间解决了操作1和2。

细节很重要。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2000000 + 10; struct Node {
int lc,rc,cnt;
}; struct segtree {
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1) int l[maxn],r[maxn],tag[maxn];
Node a[maxn];
int rev,delta,n,tmp; void trans(int &x,int &y) {
if(rev) { //反旋
x=(n-x+2-delta+n)%n;
y=(n-y+2-delta+n)%n;
swap(x,y);
}
else { //正旋
x=(x-delta+n)%n;
y=(y-delta+n)%n;
}
x=x?x:n;
y=y?y:n;
} void push(int x) {
if(!tag[x]) return;
a[lc(x)].lc=a[rc(x)].lc=tag[x];
a[lc(x)].rc=a[rc(x)].rc=tag[x];
tag[lc(x)]=tag[rc(x)]=tag[x];
a[lc(x)].cnt=a[rc(x)].cnt=1;
tag[x]=0;
} Node update(Node a,Node b) {
Node res;
res.lc=a.lc;
res.rc=b.rc;
res.cnt=a.cnt+b.cnt-(a.rc==b.lc);
return res;
} void update(int x) {
a[x]=update(a[lc(x)],a[rc(x)]);
} void build(int x,int L,int R) {
l[x]=L; r[x]=R;
if(L==R) {
scanf("%d",&tmp);
a[x].lc=a[x].rc=tmp;
a[x].cnt=1;
return;
}
int mid=(L+R)>>1;
build(lc(x),L,mid);
build(rc(x),mid+1,R);
update(x);
} void color(int x,int L,int R,int v) {
if(L>r[x] || R<l[x]) return;
if(L<=l[x] && r[x]<=R) {
tag[x]=v;
a[x].lc=a[x].rc=v;
a[x].cnt=1;
return;
}
push(x);
color(lc(x),L,R,v);
color(rc(x),L,R,v);
update(x);
} Node query(int x,int L,int R) {
if(L<=l[x] && r[x]<=R) return a[x];
int mid=(l[x]+r[x])>>1;
push(x);
if(R<=mid) return query(lc(x),L,R);
else if(L>mid) return query(rc(x),L,R);
else return update(query(lc(x),L,R),query(rc(x),L,R));
} void paws(int i,int j) {
trans(i,j);
Node cur;int ci,cj;
if(i<=j) {
cur=query(1,i,j);
ci=cur.lc; cj=cur.rc;
}
else {
cur=query(1,j,i);
cj=cur.lc; ci=cur.rc;
}
color(1,i,i,cj);
color(1,j,j,ci);
} void rotate() {
int k;
scanf("%d",&k);
if(rev) delta=(delta-k+n)%n; // 反旋
else delta=(delta+k)%n; // 正旋
} void paint(int i,int j,int v) {
trans(i,j);
if(i<=j) color(1,i,j,v);
else {
color(1,i,n,v);
color(1,1,j,v);
}
} void c1() {
Node cur;
cur=query(1,1,n);
printf("%d\n",max(cur.cnt-(cur.lc==cur.rc),1));
} void c2(int i,int j) {
trans(i,j);
Node cur;
if(i<=j) cur=query(1,i,j);
else cur=update(query(1,i,n),query(1,1,j));
printf("%d\n",cur.cnt);
} void init() {
int c;
scanf("%d%d",&n,&c);
rev=delta=0;
build(1,1,n);
}
}seg; char op[20];
int k,i,j,x,q; int main() {
seg.init();
scanf("%d",&q);
while(q--) {
scanf("%s",op);
if(op[0]=='R') seg.rotate();
else if(op[0]=='F') seg.rev^=1;
else if(op[0]=='S') {
scanf("%d%d",&i,&j);
seg.paws(i,j);
}
else if(op[0]=='P') {
scanf("%d%d%d",&i,&j,&x);
seg.paint(i,j,x);
}
else if(op[0]=='C' && op[1]=='S') {
scanf("%d%d",&i,&j);
seg.c2(i,j);
}
else seg.c1();
}
return 0;
}