更棒的线段树操作，尽在本题解中！

分析一波题意，显然的区间操作，而且信息都是线段树能维护的。

因为有区间取反操作，所以不仅要记录 $1$ 的信息，$0$ 的信息也要记录。

对于一个点，我们考虑维护 $8$ 个信息：

$1/0$ 的个数，左/右边起 $1/0$ 的最长长度，整段区间中 $1/0$ 的连续最长长度。

只有维护至少 $8$ 个信息才能保证能够合并区间（想想为什么）。

使用结构体存储复杂信息是更好的方法：

struct d{
    // 分别表示上述的8个信息
    // w: 1(white) , b: 0(black)
    // l: 左边起 , r: 右边起
    // mw, mb 代表整段区间中1/0的最长长度
    int w,b,lw,lb,rw,rb,mw,mb;
    //构造函数，方便赋值
    d(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0):
    w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
};

而合并两个子区间，需要考虑很多东西：

$1/0$ 的个数直接相加，左右起的 $1/0$ 要考虑左/右的一整个区间是否是同一个数。

整段区间中的 $1/0$ 最长长度为以下两值的较大值

• 左、右区间的 $1/0$ 最长长度；
• 左边的右端、右边的左端的 $1/0$ 最长长度之和。

由此写出合并两个区间的函数：

inline d hb(d i,d j){
	return d(
	i.w+j.w, i.b+j.b,
	(i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
	(j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
	max(max(i.mw,j.mw),i.rw+j.lw),
	max(max(i.mb,j.mb),i.rb+j.lb));
}

这个函数在建树，修改和查询的时候都会用到，我写复杂的线段树都会定义这个函数。

然后是对一个区间整体修改，要注意 $3$ 种修改操作的优先顺序：先赋值后取反：

inline void P(int i,int typ){
    // tg1(标记1)是区间赋值,没有标记时为-1,有标记时为0或1
    // tg2(标记2)是区间取反,没有标记时为 0,有标记时为1
    // len表示一个区间的长度,在建树时处理
    d&t=dat[i];
    // 区间赋值为 0
    if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
    // 区间赋值为 1
    if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
    // 区间取反
    if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
}

这个函数会在修改和标记下传（pushdown）时用到。

接下来是标记下传（pushdown），注意顺序：

inline void pd(int i){
    // 对两个子区间修改
    if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
    if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
    // 把标记清空
    tg1[i]=-1, tg2[i]=0;
}

最后是建树，修改和查询函数，有了上面的，这就很简单了：

void build(int i,int l,int r){
    len[i]=r-l+1; tg1[i]=-1;
    if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
    build(i<<1,l,l+r>>1);
    build(i<<1|1,(l+r>>1)+1,r);
    dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
void Mdf(int i,int l,int r,int a,int b,int t){
    // 如果区间没有交集 或者 当前区间完全包含在修改区间内的情况
    if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
    pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
    dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
d Qur(int i,int l,int r,int a,int b){
    // 如果区间没有交集 或者 当前区间完全包含在查询区间内的情况
    if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
    pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));
}

下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,q,a[100001];
struct d{
	int w,b,lw,lb,rw,rb,mw,mb;
	d(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0):
    w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
};
inline d hb(d i,d j){
	return d(
	i.w+j.w, i.b+j.b,
	(i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
	(j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
	max(max(i.mw,j.mw),i.rw+j.lw),
	max(max(i.mb,j.mb),i.rb+j.lb));
}
d dat[262144]; int len[262144],tg1[262144],tg2[262144];
inline void P(int i,int typ){
	d&t=dat[i];
	if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
	if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
	if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
}
inline void pd(int i){
	if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
	if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
	tg1[i]=-1, tg2[i]=0;
}
void build(int i,int l,int r){
	len[i]=r-l+1; tg1[i]=-1;
	if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
	build(i<<1,l,l+r>>1);
	build(i<<1|1,(l+r>>1)+1,r);
	dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
void Mdf(int i,int l,int r,int a,int b,int t){
	if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
	pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
	dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
d Qur(int i,int l,int r,int a,int b){
	if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
	pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	build(1,1,n);
	for(int i=1;i<=q;++i){
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r); ++l, ++r;
		if(opt<3) Mdf(1,1,n,l,r,opt);
		else {d t=Qur(1,1,n,l,r); printf("%d\n",opt==3?t.w:t.mw);}
	}
	return 0;
}

以上就是我打较复杂线段树操作时的模板，大家可以借鉴一下，形成自己的风格。

更棒的 bitset 操作，尽在本题解中！

传统 bitset

观察到这题的数据范围是 $10^5$，而且全是 $01$ 串，因此联想到 $O(n^2w^{-1})$ 的 bitset。（本文中 $w$ 均表示字长，默认 $64$）。

传统的 bitset 可以借助位运算轻松地维护区间置 $0$、区间置 $1$、区间翻转，时间复杂度均为 $O(n/w)$。而且这三者代码极为接近，一般写完一个稍微改改就能得到另一个。

同时借助 __builtin_popcountll 函数（时间复杂度 $O(\log w)$，我们可以写出区间数 $1$ 的代码。

难点

但是区间数连续 $1$ 数并不好维护——哪怕维护同一 int64 的前缀、后缀 $1$ 数量可以用 lowbit 和 __lg 解决，同块连续 $1$ 数量也没有对应的位运算手段。

因此我们对于这种操作我们只能放弃位运算，直接将一块内所有情形全部预处理出左侧 $1$ 数、右侧 $1$ 数、连续 $1$ 数。

这也就导致对于这种运算我们选取的块长不能是 $64$ 了（我选的 $16$，也就是一大块变四小块，要是有人不怕麻烦可以选 $21,21,22$），但是前几种操作我们依然可以选 $64$。

注意事项 & 调试技巧

• unsigned long long 溢出是有定义的，long long 溢出算 UB。
• 当你要取二进制某一位时请写成 1ull<<x（而非 1<<x），否则会导致溢出。
• 大部分同学用小端法 bitset 存储（也就是 $2^0$ 位对应 $seq_0$），但是左移右移运算仍然建立在大端法基础上，因此两种记法不要弄混。
• （适用于所有题目） 你认为是难点、最容易出错的地方可能反而没那么容易出错，比如这道题我一直在 $4$ 操作上找问题找了一下午，最后发现是 $0$ 操作有一处 $l,r$ 写成 $bl,br$ 了。

#include<bits/stdc++.h>
using namespace std;
const int Rsh=6,B=1<<Rsh,B4=16,Bmx=65535;
//块长是2的Rsh次方也就是B，特别地，4操作块长为 B4，块内最大值Bmx
int n,m,cb[1<<16],l1[1<<16],r1[1<<16];
unsigned long long a[1565],op[64][64];
//op[l][r]为二进制第l..r位均为 1 的二进制数，为减小位运算打错概率我设计成这样
void set0(int l,int r)//[l,r]
{
	int bl=l>>Rsh,br=r>>Rsh;
	l&=B-1;r&=B-1;
	if(bl==br)//特判同一块
	{
		a[bl]&=~op[l][r];
		return;
	}
	a[bl]&=~op[l][B-1];
	a[br]&=~op[0][r];
	for(int i=bl+1;i<br;i++)
		a[i]=0;
}
void set1(int l,int r)
{
	int bl=l>>Rsh,br=r>>Rsh;
	l&=B-1;r&=B-1;
	if(bl==br)
	{
		a[bl]|=op[l][r];
		return;
	}
	a[bl]|=op[l][B-1];
	a[br]|=op[0][r];
	for(int i=bl+1;i<br;i++)
		a[i]=-1ull;
}
void rev(int l,int r)
{
	int bl=l>>Rsh,br=r>>Rsh;
	l&=B-1;r&=B-1;
	if(bl==br)
	{
		a[bl]^=op[l][r];
		return;
	}
	a[bl]^=op[l][B-1];
	a[br]^=op[0][r];
	for(int i=bl+1;i<br;i++)
		a[i]^=-1ull;
}
#define BPL __builtin_popcountll 
int countbit(int l,int r)
{
	int bl=l>>Rsh,br=r>>Rsh;
	l&=B-1;r&=B-1;
	if(bl==br)
		return BPL(a[bl]&op[l][r]);
	int tot=BPL(a[bl]&op[l][B-1])+BPL(a[br]&op[0][r]);
	for(int i=bl+1;i<br;i++)
		tot+=BPL(a[i]);
	return tot;
}
int combo(int l,int r)
{
	if((l>>4)==(r>>4))//其实这不是必须，见后面代码
		return cb[(a[l>>Rsh]&op[l&(B-1)][r&(B-1)])>>(l&(B-1))];
	int bl=l>>Rsh,br=r>>Rsh,overall=0,mxr=0;
    //overall记录当前所有连续1最大值，mxr记录当前有几个连续的1
	unsigned long long RealAbl=a[bl],RealAbr=a[br];
    //为节省讨论，我们将干扰清空，完事重新写入
	a[bl]&=op[l&(B-1)][B-1];a[br]&=op[0][r&(B-1)];
	for(int i=bl;i<=br;i++)
	{
		for(int j=1;j<=4;j++)
		{
			unsigned long long v=a[i]<<(B-j*B4)>>(3*B4);//请注意，这里涉及大端法和小端法的区别
			if(v==Bmx)//如果这块全 1
			{
				overall=max(overall,mxr+B4);
				mxr+=B4;
			}
			else
			{
				overall=max(overall,max(mxr+r1[v],cb[v]));
				mxr=l1[v];
			}
		}
	}
	a[bl]=RealAbl;a[br]=RealAbr;
	return overall;
}
int main()
{
	for(int i=0;i<B;i++)//预处理 op数组
	{
		op[i][i]=1ull<<i;
		for(int j=i+1;j<B;j++)
			op[i][j]=op[i][j-1]|(1ull<<j);
	}
	for(int i=0;i<(1<<B4);i++)
	{
		if(i&1)r1[i]=r1[i>>1]+1;//大端法右侧 1 个数
		else r1[i]=0;
		cb[i]=max(cb[i>>1],r1[i]);//块内最大连续 1 个数
		for(int j=i;j&(1<<B4-1);j=(j<<1)^(1<<B4))l1[i]++;//大端法左侧 1 个数，反正不是瓶颈，多个log无所谓了
	}
	scanf("%d%d",&n,&m);
	unsigned long long tmp;
	for(int i=0;i<n;i++)
	{
		scanf("%llu",&tmp);
		a[i>>Rsh]|=tmp<<(i&(B-1));
	}
	int op,l,r;
	for(;m;m--)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==0)set0(l,r);
		if(op==1)set1(l,r);
		if(op==2)rev(l,r);
		if(op==3)printf("%d\n",countbit(l,r));
		if(op==4)printf("%d\n",combo(l,r));
	}
	return 0;
}

C36 线段树 P2572 [SCOI2010] 序列操作

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define mid ((tr[p].l+tr[p].r)>>1)
const int N=1e5+10;
int n,m,a[N];
struct trnode
{
    int l,r;
    int b,lb,rb,mb,c,lc,rc,mc;
    int tag,rev;
}tr[N<<2];
// b:区间1的个数,      c:区间0的个数
//lb:区间左起1的长度, lc:区间左起0的长度
//rb:区间右起1的长度, rc:区间右起0的长度
//mb:区间1的最长长度, mc:区间0的最长长度
//tag:区间赋值标记,无标记:-1,有标记:0或1
//rev:区间取反标记,无标记: 0,有标记:1
void pd(int p,int op)//操作区间
{
    trnode &t=tr[p];
    if(op==0)//区间赋值为0
    {
        t.b=t.lb=t.rb=t.mb=0;
        t.c=t.lc=t.rc=t.mc=t.r-t.l+1;
        t.tag=0; t.rev=0;
    }
    if(op==1)//区间赋值为1
    {
        t.b=t.lb=t.rb=t.mb=t.r-t.l+1;
        t.c=t.lc=t.rc=t.mc=0;
        t.tag=1; t.rev=0;
    }
    if(op==2)//区间取反
    {
        swap(t.b,t.c);swap(t.lb,t.lc);
        swap(t.rb,t.rc);swap(t.mb,t.mc);
        t.rev^=1;
    }
}
void merge(trnode& t,trnode l,trnode r)//合并
{
    t.b=l.b+r.b;
    t.lb=l.c ? l.lb : l.b+r.lb;
    t.rb=r.c ? r.rb : r.b+l.rb;
    t.mb=max(max(l.mb,r.mb),l.rb+r.lb);
    t.c=l.c+r.c;
    t.lc=l.b ? l.lc : l.c+r.lc;
    t.rc=r.b ? r.rc : r.c+l.rc;
    t.mc=max(max(l.mc,r.mc),l.rc+r.lc);
	
}

void pushdown(int p)//下传
{
    if(tr[p].tag==0) pd(lc(p),0),pd(rc(p),0);
    if(tr[p].tag==1) pd(lc(p),1),pd(rc(p),1);
    if(tr[p].rev) pd(lc(p),2),pd(rc(p),2);
    tr[p].tag=-1;tr[p].rev=0;
}
void bt(int p,int l,int r)//建树
{
    int t=a[l];
    tr[p]={l,r,t,t,t,t,t^1,t^1,t^1,t^1,-1,0};
    if(l==r) return;
    bt(lc(p),l,mid); bt(rc(p),mid+1,r);
    merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
void change(int p,int l,int r,int op)//区修
{
    if(r<tr[p].l || tr[p].r<l) return;
    if(l<=tr[p].l&&tr[p].r<=r){ pd(p,op);return; }
    pushdown(p);
    change(lc(p),l,r,op);change(rc(p),l,r,op);
    merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
trnode query(int p,int l,int r)//区查
{
    if(r< tr[p].l || tr[p].r< l) return {};
    if(l<=tr[p].l && tr[p].r<=r) return tr[p];
    pushdown(p);
    trnode t; //开一个临时节点，存储拼凑结果
    merge(t,query(lc(p),l,r),query(rc(p),l,r));
    return t;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    bt(1,1,n);
    for(int i=1,op,l,r;i<=m;i++)
    {
        scanf("%d%d%d",&op,&l,&r); ++l,++r;
        if(op<3) change(1,l,r,op);
        else
        {
            trnode t=query(1,l,r);
            printf("%d\n",op==3?t.b:t.mb);
        }
    }
    return 0;
}