[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;
}

加入对话

3条评论

  1. ym….不过俺还有几个细节问题,传标记为啥要传两层呢,还有查询的时候一定要更新吗,如果路径上的某个区间有标记的话,直接返回0或者r-l+1就行啊。大牛莫见怪啊

  2. 回复右上角那三头猪:update的作用是从下面一层传数据上来,但是如果下面一层的数据并没有标记下传的话,它的数据是不正确的!另外查询的时候,我更新是为了让当前的标记传下去,使得当前这个结点的数据是正确的,当然,由于这题比较特殊,如果遇到操作0和操作1的标记,确实是可以直接返回答案的。但是如果一路都只是翻转呢?那么就需要一直标记下传,直到到达目标区间,并取出正确的数据。

  3. 回复edward_mj:orz,明白了,如果数据往上传的时候某个子区间有覆盖或者有filp没来得及下传,好像就和数据对不上了 – – PS:您的代码很清楚,看起来很舒服。

留下评论

您的电子邮箱地址不会被公开。