题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1858
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）
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
对于30%的数据，1<=n, m<=1000 对于100%的数据，1< = n, m < = 100000
题解：
考虑怎么对标记进行维护，使用full标记判断该节点所代表的区间是否是同一数字；c标记代表0/1操作，将该节点全部赋值，同时更新full标记
在翻转标记rev的下推过程中注意偶数次翻转等于没有操作，而赋值操作会清空rev标记。在程序中我们考虑另写一个color函数来将节点染色（全部赋值一个数）
关键之处在于合并，对于连续的1的个数其实很好维护，细节在于l0,l1,r0,r1即从区间左边到右边和右边到左边有多少个连续的1；值得注意的是合并操作返回的是一颗子树
那么在统计最大连续的1的时候，我们不能采取累加的方式，而是要在指定区间里合并出一颗新的树，直接输出它的mx1，即最大的连续1的个数
笔者强调，本题细节较多，请读者耐心阅读并尝试自己打完代码
#include<iostream> #include<cstdio> #include<algorithm> #define N 100005 using namespace std; int n,m; int a[N]; struct seg { int l,r; int l0,l1,r0,r1,mx0,mx1,sum0,sum1; int rev,c,full; }t[N<<2]; void rev(int k) { swap(t[k].l0,t[k].l1); swap(t[k].r0,t[k].r1); swap(t[k].mx0,t[k].mx1); swap(t[k].sum0,t[k].sum1); if(t[k].full!=-1)t[k].full^=1; } void color(int k,int v) { t[k].rev=0; int s=t[k].r-t[k].l+1; if(v==0) { t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=s; t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=0; } else { t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=0; t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=s; } t[k].full=v; } seg merge(seg a,seg b) { seg tmp;tmp.l=a.l;tmp.r=b.r; tmp.rev=0;tmp.c=-1; tmp.l0=a.l0;tmp.l1=a.l1; tmp.r0=b.r0;tmp.r1=b.r1; tmp.mx0=max(a.mx0,b.mx0); tmp.mx1=max(a.mx1,b.mx1); tmp.mx0=max(tmp.mx0,a.r0+b.l0); tmp.mx1=max(tmp.mx1,a.r1+b.l1); tmp.sum0=a.sum0+b.sum0; tmp.sum1=a.sum1+b.sum1; if(a.full==0)tmp.l0=a.mx0+b.l0; else if(a.full==1)tmp.l1=a.mx1+b.l1; if(b.full==0)tmp.r0=b.mx0+a.r0; else if(b.full==1)tmp.r1=b.mx1+a.r1; if(a.full==b.full) tmp.full=a.full; else tmp.full=-1; return tmp; } void pushup(int k) { t[k]=merge(t[k<<1],t[k<<1|1]); } void pushdown(int k) { if(t[k].l==t[k].r)return; if(t[k].c!=-1) { t[k<<1].c=t[k<<1|1].c=t[k].c; color(k<<1,t[k].c);color(k<<1|1,t[k].c); t[k].c=-1; } if(t[k].rev) { t[k<<1].rev^=1; t[k<<1|1].rev^=1; rev(k<<1);rev(k<<1|1); t[k].rev=0; } } void build(int k,int l,int r) { t[k].l=l;t[k].r=r; t[k].c=-1; if(l==r) { t[k].full=a[l]; if(t[k].full) {t[k].l1=t[k].r1=t[k].mx1=t[k].sum1=1;} else {t[k].l0=t[k].r0=t[k].mx0=t[k].sum0=1;} return; } int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void change(int k,int x,int y,int v) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&r==y) { color(k,v); t[k].c=v; return; } int mid=(l+r)>>1; if(mid>=y)change(k<<1,x,y,v); else if(mid<x)change(k<<1|1,x,y,v); else { change(k<<1,x,mid,v); change(k<<1|1,mid+1,y,v); } pushup(k); } void rever(int k,int x,int y) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&r==y) { rev(k); t[k].rev=1; return; } int mid=(l+r)>>1; if(mid>=y)rever(k<<1,x,y); else if(mid<x)rever(k<<1|1,x,y); else { rever(k<<1,x,mid); rever(k<<1|1,mid+1,y); } pushup(k); } seg ask(int k,int x,int y) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r)return t[k]; int mid=(l+r)>>1; if(mid>=y)return ask(k<<1,x,y); else if(mid<x)return ask(k<<1|1,x,y); else return merge(ask(k<<1,x,mid),ask(k<<1|1,mid+1,y)); } int asksum(int k,int x,int y) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r)return t[k].sum1; int mid=(l+r)>>1; if(mid>=y)return asksum(k<<1,x,y); else if(mid<x)return asksum(k<<1|1,x,y); else return asksum(k<<1,x,mid)+asksum(k<<1|1,mid+1,y); } int main() { //freopen("a.in","r",stdin); //freopen("b.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for(int i=1;i<=m;i++) { int f,x,y; scanf("%d%d%d",&f,&x,&y); x++;y++; switch(f) { case 0:change(1,x,y,0);break; case 1:change(1,x,y,1);break; case 2:rever(1,x,y);break; case 3:printf("%d\n",asksum(1,x,y));break; case 4:printf("%d\n",ask(1,x,y).mx1);break; } } return 0; }
[BZOJ1858] [SCOI2010] 序列操作 解题报告 (线段树)
原文：https://www.cnblogs.com/xxzh/p/9351147.html