自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:39:13，当前版本为作者最后更新于2018-05-26 00:08:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

因为有区间取反操作，所以不仅要记录 $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;
}

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