刷题记录:牛客NC20279[SCOI2010]序列操作

传送门:牛客

题目描述:

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都需要给出回答，聪明的程序员们，你们能帮助他吗？
输入:
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
输出:
5
2
6
5

此题维护方式较为麻烦,需要考虑多种因素,成功写出此题之后对线段树的理解将会大大上升!!

看完题目,我们会发现显然与区间的01数量有关,并且与连续性有关

考虑用$lazy=0/1$来记录区间是否被置为$0/1$,用$rev$来记录区间是否取反
用$sum[0/1]$来记录区间连续的$0/1$的数量,$tot$来记录区间$1$的数量

然后我们分析一个区间$[l,r]$的连续的1的数量该如何计算,我们发现可以分为3中情况,一种是该连续区间在左区间$[l,mid]$,一种是该连续区间在$[mid+1,r]$,还有一种是该连续区间横跨区间$[l,r]$.对于前两种情况,我们发现$sum[0/1]$已经记录下来了.对于最后一种情况,我们发现光靠上述变量无法维护.所以此时我们使用$lmax[0/1]$来记录从区间的前缀$0/1$的最大连续数量,$rmax[0/1]$来记录区间的后缀$0/1$的最大连续数量.那么此时对于第三种情况显然就是左子树的$lmax[1]$+右子树的$rmax[1]$

现在我们来分析如何进行维护.

对于$pushup$:

$tot$可以直接维护.对于$sum[]$,我们则需要枚举上述的三种情况来进行维护
对于$lmax$我们则需要判断连续区间是否能跨区间.也就是说连续的数字能否从左边界一直连续到右边界
对于$rmax$,与$lmax$同理

对于$update$:

1. 对$[l,r]$区间置0.此时我们的$sum[],lazy,tot,lmax,rmax$修改方式不难.需要注意的是,此时我们的修改会覆盖掉之前的$rev$,也就是说无论之前是否进行过取反,此时我们的值都是0
2. 对$[l,r]$区间置1.此时我们的方法和上述相同
3. 对[l,r]进行取反.注意此时如果我们的区间有$lazy$,那就意味着我们的区间是相同的$0/1$,此时我们可以直接改$lazy$(这样做的好处是,当我们的子区间进行继承时,如果有父亲既有$lazy$,又有$rev$,可以直接对$lazy$进行操作,忽略$rev$).对于$sum[],lazy,tot,lmax,rmax$,我们直接调换$0/1$的值即可

对于$pushdown$:

修改的方式和$update$相同,由父亲的$lazy$控制.需要注意的是如果有父亲既有$lazy$,又有$rev$,可以直接对$lazy$进行操作,忽略$rev$,因为在父亲的$update$过程中,我们已经对$lazy$进行了相应操作

对于$query1$(找1的个数):

直接返回对应区间的$tot$即可

对于$query2$(找最长的连续1):

对于一个区间连续的1我们有三种情况(在之前分析过).对三种情况取一个$max$即可

---

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r;int rmax[2],lmax[2];//记录01前后缀长度int lazy,rev;//lazy记录是否被置0/1,rev记录是否被取反int sum[2];//sum1/0记录区间内最长的连续1/0的个数int tot;//记录区间内1的个数
}tree[maxn*4];
int n,m;int a[maxn];
void pushup(int rt) {int lenls=tree[ls].r-tree[ls].l+1;int lenrs=tree[rs].r-tree[rs].l+1;tree[rt].tot=tree[ls].tot+tree[rs].tot;for(int i=0;i<=1;i++) {tree[rt].sum[i]=max(tree[ls].sum[i],tree[rs].sum[i]);tree[rt].sum[i]=max(tree[rt].sum[i],tree[ls].rmax[i]+tree[rs].lmax[i]);if(tree[ls].lmax[i]==lenls) tree[rt].lmax[i]=lenls+tree[rs].lmax[i];else tree[rt].lmax[i]=tree[ls].lmax[i];if(tree[rs].rmax[i]==lenrs) tree[rt].rmax[i]=lenrs+tree[ls].rmax[i];else tree[rt].rmax[i]=tree[rs].rmax[i];}
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;tree[rt].lazy=-1;if(l==r) {if(a[l]&1) {tree[rt].rmax[1]=tree[rt].lmax[1]=1;tree[rt].sum[1]=1;tree[rt].tot=1;}else {tree[rt].rmax[0]=tree[rt].lmax[0]=1;tree[rt].sum[0]=1;}return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void change(int rt,int opt) {int len=tree[rt].r-tree[rt].l+1;if(opt==0) {tree[rt].lazy=0;tree[rt].tot=0;tree[rt].sum[0]=len;tree[rt].sum[1]=0;tree[rt].rev=0;tree[rt].lmax[0]=len;tree[rt].lmax[1]=0;tree[rt].rmax[0]=len;tree[rt].rmax[1]=0;}else if(opt==1) {tree[rt].lazy=1;tree[rt].tot=len;tree[rt].sum[1]=len;tree[rt].sum[0]=0;tree[rt].rev=0;tree[rt].lmax[1]=len;tree[rt].lmax[0]=0;tree[rt].rmax[1]=len;tree[rt].rmax[0]=0;}else {if(tree[rt].lazy!=-1) {tree[rt].lazy^=1;}tree[rt].rev^=1;tree[rt].tot=len-tree[rt].tot;swap(tree[rt].lmax[0],tree[rt].lmax[1]);swap(tree[rt].rmax[0],tree[rt].rmax[1]);swap(tree[rt].sum[0],tree[rt].sum[1]);}
}
void pushdown(int rt) {if(tree[rt].lazy!=-1) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].rev=0;tree[rt].lazy=-1;}else {change(ls,2);change(rs,2);tree[rt].rev=0;tree[rt].lazy=-1;}
}
void update(int l,int r,int rt,int opt) {if(tree[rt].l==l&&tree[rt].r==r) {change(rt,opt);return ;}if(tree[rt].lazy!=-1||tree[rt].rev) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) update(l,r,ls,opt);else if(l>mid) update(l,r,rs,opt);else update(l,mid,ls,opt),update(mid+1,r,rs,opt);pushup(rt);
}
int query1(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt].tot;}if(tree[rt].lazy!=-1||tree[rt].rev) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query1(l,r,ls);else if(l>mid) return query1(l,r,rs);else return query1(l,mid,ls)+query1(mid+1,r,rs);
}
int query2(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt].sum[1];} if(tree[rt].lazy!=-1||tree[rt].rev) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query2(l,r,ls);else if(l>mid) return query2(l,r,rs);else {int ans=max(query2(l,mid,ls),query2(mid+1,r,rs));int rm=min(tree[ls].rmax[1],mid-l+1);int lm=min(tree[rs].lmax[1],r-mid);ans=max(ans,lm+rm);return ans;}
}
int main() {n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,n+10,1);for(int i=1;i<=m;i++) {int opt=read(),l=read(),r=read();l++;r++;if(opt==0) {update(l,r,1,0);}else if(opt==1) {update(l,r,1,1);}else if(opt==2) {update(l,r,1,2);}else if(opt==3) {printf("%d\n",query1(l,r,1));}else {printf("%d\n",query2(l,r,1));}}return 0;
}