【题目】

传送门

题目描述：

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

输入格式：

输入数据第一行包括 $2$ 个数，$n$ 和 $m$，分别表示序列的长度和操作数目

第二行包括 $n$ 个数，表示序列的初始状态

接下来 $m$ 行，每行 $3$ 个数，$op,a,b$，（$0$ ≤ $op$ ≤ $4$，$0$ ≤ $a$ ≤ $b$ < $n$）表示对于区间 [ $a$ , $b$ ] 执行标号为 $op$ 的操作

输出格式：

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

样例数据：

输入 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

说明：

【数据范围】 对于 $30\%$ 的数据，$1$ ≤ $n,m$ ≤ $1000$ 对于 $100\%$ 的数据，$1$ ≤ $n,m$ ≤ $100000$

【分析】

题解：线段树，支持区间覆盖，区间取反，区间求和，区间求最大连续子段

其实这几个操作都是基础的操作，但由于代码能力较弱，硬是调了很久

应该算是一道好题吧，比较综合，把很多东西都一次就考到了

代码还是比较简洁，不算很长，但还是有很多细节

【代码】

#include<cstdio> #include<cstring> #include<algorithm> #define N 100005 using namespace std; int a[N]; struct node { int L[2],R[2],Max[2],sum[2],len,change,cover; }Seg[N<<2]; node update(node left,node right) { node root; root.change=0,root.cover=-1; root.len=left.len+right.len; for(int i=0;i<=1;++i) { root.sum[i]=left.sum[i]+right.sum[i]; root.L[i]=(left.L[i]==left.len?left.L[i]+right.L[i]:left.L[i]); root.R[i]=(right.R[i]==right.len?right.R[i]+left.R[i]:right.R[i]); root.Max[i]=max(max(left.Max[i],right.Max[i]),left.R[i]+right.L[i]); } return root; } void Build(int root,int l,int r) { if(l==r) { Seg[root].change=0,Seg[root].cover=-1,Seg[root].len=1; Seg[root].L[a[l]]=Seg[root].R[a[l]]=Seg[root].Max[a[l]]=Seg[root].sum[a[l]]=1; return; } int mid=(l+r)>>1; Build(root<<1,l,mid); Build(root<<1|1,mid+1,r); Seg[root]=update(Seg[root<<1],Seg[root<<1|1]); } void Cover(int root,int l,int r,int val) { Seg[root].cover=val;Seg[root].change=0; Seg[root].L[val]=Seg[root].R[val]=Seg[root].Max[val]=Seg[root].sum[val]=r-l+1; Seg[root].L[val^1]=Seg[root].R[val^1]=Seg[root].Max[val^1]=Seg[root].sum[val^1]=0; } void Change(int root) { Seg[root].change^=1; swap(Seg[root].L[0],Seg[root].L[1]); swap(Seg[root].R[0],Seg[root].R[1]); swap(Seg[root].sum[0],Seg[root].sum[1]); swap(Seg[root].Max[0],Seg[root].Max[1]); } void Pushdown(int root,int l,int r,int mid) { if(Seg[root].cover!=-1) Cover(root<<1,l,mid,Seg[root].cover),Cover(root<<1|1,mid+1,r,Seg[root].cover); if(Seg[root].change) Change(root<<1),Change(root<<1|1); Seg[root].cover=-1,Seg[root].change=0; } void Modify(int root,int l,int r,int x,int y,int k) { if(l>=x&&r<=y) { Cover(root,l,r,k); return; } int mid=(l+r)>>1; Pushdown(root,l,r,mid); if(x<=mid) Modify(root<<1,l,mid,x,y,k); if(y>mid) Modify(root<<1|1,mid+1,r,x,y,k); Seg[root]=update(Seg[root<<1],Seg[root<<1|1]); } void Negate(int root,int l,int r,int x,int y) { if(l>=x&&r<=y) { Change(root); return; } int mid=(l+r)>>1; Pushdown(root,l,r,mid); if(x<=mid) Negate(root<<1,l,mid,x,y); if(y>mid) Negate(root<<1|1,mid+1,r,x,y); Seg[root]=update(Seg[root<<1],Seg[root<<1|1]); } node Query(int root,int l,int r,int x,int y) { if(l>=x&&r<=y) return Seg[root]; int mid=(l+r)>>1; Pushdown(root,l,r,mid); if(y<=mid) return Query(root<<1,l,mid,x,y); if(x>mid) return Query(root<<1|1,mid+1,r,x,y); return update(Query(root<<1,l,mid,x,y),Query(root<<1|1,mid+1,r,x,y)); } int main() { int n,m,i,s,x,y; scanf("%d%d",&n,&m); for(i=1;i<=n;++i) scanf("%d",&a[i]); Build(1,1,n); for(i=1;i<=m;++i) { scanf("%d%d%d",&s,&x,&y);x++,y++; if(s==0) Modify(1,1,n,x,y,0); if(s==1) Modify(1,1,n,x,y,1); if(s==2) Negate(1,1,n,x,y); if(s==3) printf("%d\n",Query(1,1,n,x,y).sum[1]); if(s==4) printf("%d\n",Query(1,1,n,x,y).Max[1]); } return 0; }