[SCOI 第二试 序列操作]线段树

【题目】

Description

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

Input

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目
第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

Hint

对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000 【算法分析】
就是线段树。但是注意标记下传的函数要写好，下传覆盖为0或覆盖为1的标记的时候，需要把儿子原本的标记都删掉（因为之前的标记在这个覆盖后都没有用了）。
然后处理标记就先搞覆盖，再弄翻转。因为如果是覆盖操作在后的话，那么所有标记都会消失，而现在标记共存的话，肯定是先覆盖再翻转。注意了这一点以后就很容易AC了。
【CODE】
#include #include #include #include using namespace std;
const int N=100005;
int n,m;
int a[N];
struct Treetype{
struct Node{int l,r,FL0,FL1,FR0,FR1,N0,N1,L0,L1,c0,c1,filp;}tr[N*5];

void pushdown(int pos){
Node &p=tr[pos];
if (p.c0){
p.FL0=p.FR0=p.N0=p.L0=p.r-p.l+1;
p.FL1=p.FR1=p.N1=p.L1=0;
p.c0=0;
if (p.l!=p.r){
tr[pos*2].c0=1;
tr[pos*2].c1=0;
tr[pos*2].filp=0;
tr[pos*2+1].c0=1;
tr[pos*2+1].c1=0;
tr[pos*2+1].filp=0;
}
}
if (p.c1){
p.FL0=p.FR0=p.N0=p.L0=0;
p.FL1=p.FR1=p.N1=p.L1=p.r-p.l+1;
p.c1=0;
if (p.l!=p.r){
tr[pos*2].c1=1;
tr[pos*2].c0=0;
tr[pos*2].filp=0;
tr[pos*2+1].c1=1;
tr[pos*2+1].c0=0;
tr[pos*2+1].filp=0;
}
}
if (p.filp){
swap(p.FL0,p.FL1);
swap(p.FR0,p.FR1);
swap(p.N0,p.N1);
swap(p.L0,p.L1);
if (p.l!=p.r){
tr[pos*2].filp^=1;
tr[pos*2+1].filp^=1;
}
p.filp=0;
}
}

void update(int pos){
Node &p=tr[pos];
pushdown(pos);
if (p.l!=p.r){
pushdown(pos*2);
pushdown(pos*2+1);
}
if (p.l==p.r) return;
Node &L=tr[pos*2],&R=tr[pos*2+1];
p.N0=L.N0+R.N0;
p.N1=L.N1+R.N1;
p.L0=max(L.L0,R.L0); p.L0=max(p.L0,L.FR0+R.FL0);
p.L1=max(L.L1,R.L1); p.L1=max(p.L1,L.FR1+R.FL1);
p.FL0=L.FL0; if (L.FL0==L.r-L.l+1) p.FL0+=R.FL0;
p.FL1=L.FL1; if (L.FL1==L.r-L.l+1) p.FL1+=R.FL1;
p.FR0=R.FR0; if (R.FR0==R.r-R.l+1) p.FR0+=L.FR0;
p.FR1=R.FR1; if (R.FR1==R.r-R.l+1) p.FR1+=L.FR1;
}

void build(int pos,int l,int r){
Node &p=tr[pos];
p.l=l; p.r=r; p.c0=p.c1=p.filp=0;
if (l==r){
if (a[l]){
p.FL0=p.FR0=p.N0=p.L0=0;
p.FL1=p.FR1=p.N1=p.L1=1;
}
else{
p.FL0=p.FR0=p.N0=p.L0=1;
p.FL1=p.FR1=p.N1=p.L1=0;
}
return;
}
int mid=(l+r)/2;
build(pos*2,l,mid);
build(pos*2+1,mid+1,r);
update(pos);
}

void ins(int pos,int l,int r,int op){
Node &p=tr[pos];
if (r update(pos);
if (l<=p.l && p.r<=r){
switch (op){
case 0:p.c0=1; break;
case 1:p.c1=1; break;
case 2:if (p.filp) for (;;); p.filp^=1; break;
}
update(pos);
return;
}
ins(pos*2,l,r,op);
ins(pos*2+1,l,r,op);
update(pos);
}

void solve3(int pos,int l,int r,int &ans){
Node &p=tr[pos];
if (r update(pos);
if (l<=p.l && p.r<=r){
ans+=p.N1;
return;
}
solve3(pos*2,l,r,ans);
solve3(pos*2+1,l,r,ans);
}

void solve4(int pos,int l,int r,int &rr,int &ans){
Node &p=tr[pos];
if (r update(pos);
if (l<=p.l && p.r<=r){
ans=max(ans,p.L1);
ans=max(ans,rr+p.FL1);
if (p.L1==p.r-p.l+1) rr+=p.L1;
else rr=p.FR1;
ans=max(ans,rr);
return;
}
solve4(pos*2,l,r,rr,ans);
solve4(pos*2+1,l,r,rr,ans);
}
}Tree;

int main(){
freopen("operation.in","r",stdin);
freopen("operation.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
Tree.build(1,1,n);
for (int i=1;i<=m;i++){
int x,y,op;
scanf("%d%d%d",&op,&x,&y);
x++; y++;
if (op<=2) Tree.ins(1,x,y,op);
if (op==3){
int ans=0;
Tree.solve3(1,x,y,ans);
printf("%dn",ans);
}
if (op==4){
int tmp=0,ans=0;
Tree.solve4(1,x,y,tmp,ans);
printf("%dn",ans);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}