题解：Black And White / Flip and Combos

题目

题目描述

给你一个长度为n的01序列 a[1],…,a[n]

每次询问给定一个区间[l,r]，询问[l,r]里最长的连续的1的长度

每次修改给定一个区间[l,r]，将[l,r]里的a[i]变成1-a[i]（或者说异或1）

n, m <= 100000

输入格式

第一行一个n

第二行n个数，表示01序列初始状态

第三行一个m，接下来m行，每行有三个数x,l,r

若 x=0，表示一次查询，查询[l,r]里的最长连续1的长度

若 x=1，表示一次修改，将[l,r]里的数异或1

输出格式

对于输入里的每一个查询，输出一行一个整数，该询问的最长连续1的长度

---

思路

维护最长子串是经典的线段树，由于有01翻转修改，所以不能只存连续1串，也要存0.

思路可能和GSS有点像，都是维护区间最长前缀、后缀和子串（GSS是子序列），修改就翻转+重新pushup就行了。

其实不是很困难，但是线段树写起来非常易错（因为我很菜orz）

---

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=100005;

ll n,m;
ll a[N];

struct node
{
	ll l[2],r[2],mx[2]; //最长前缀，最长后缀，最长子串 
	bool lz; //懒惰标记
} tr[N*4];

void pushup(ll p,ll l,ll r) 
{
	ll mid=l+r>>1;
	
	for(ll i=0;i<2;i++)
	{
		tr[p].l[i]=tr[p<<1].l[i];
		if(tr[p<<1].l[i]==mid-l+1) //如果左半个区间全是i，前缀加上右半个区间
		{
			tr[p].l[i]+=tr[p<<1|1].l[i];	
		}
		tr[p].r[i]=tr[p<<1|1].r[i];
		if(tr[p<<1|1].r[i]==r-mid) //如果右半个区间全是i，后缀加上左半个区间
		{
			tr[p].r[i]+=tr[p<<1].r[i];
		}
		tr[p].mx[i]=max(max(tr[p<<1].mx[i],tr[p<<1|1].mx[i]),tr[p<<1].r[i]+tr[p<<1|1].l[i]);
	}
}

void flip(ll p) //翻转修改 
{
	swap(tr[p].l[0],tr[p].l[1]);
	swap(tr[p].r[0],tr[p].r[1]);
	swap(tr[p].mx[0],tr[p].mx[1]);
}

void pushdown(ll p,ll l,ll r)
{
	if(l!=r)
	{
		tr[p<<1].lz^=1;
		tr[p<<1|1].lz^=1;
		flip(p<<1),flip(p<<1|1); //左儿子右儿子继续翻转
		
		tr[p].lz=0;
	}
}

void build(ll p,ll l,ll r)
{
	tr[p].lz=0;
	if(l==r) //叶子区间赋值，写得比较无用抽象
	{
		for(ll i=0;i<2;i++)
		{
			ll j=i;
			if(a[l]==0) 
			{
				j^=1;
			}
			tr[p].l[i]=tr[p].r[i]=tr[p].mx[i]=j;
		}
		return ;
	}
	
	ll mid=l+r>>1;
	
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	
	pushup(p,l,r);
}


void update(ll p,ll l,ll r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		tr[p].lz^=1;
		flip(p);
		return ;
	}
	
	if(tr[p].lz)
	{
		pushdown(p,l,r);
	}
	
	ll mid=l+r>>1;
	if(mid>=y)
	{
		update(p<<1,l,mid,x,y);
	}
	else if(mid<x)
	{
		update(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		update(p<<1,l,mid,x,y);
		update(p<<1|1,mid+1,r,x,y);	
	}
	
	pushup(p,l,r);
}

ll query(ll p,ll l,ll r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		return tr[p].mx[1];
	}
	
	if(tr[p].lz)
	{
		pushdown(p,l,r);
	}
	
	ll mid=l+r>>1;
	if(mid>=y)
	{
		return query(p<<1,l,mid,x,y);
	}
	else if(mid<x)
	{
		return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		ll m1=query(p<<1,l,mid,x,y); //左半个区间的mx
		ll m2=query(p<<1|1,mid+1,r,x,y); //右半个区间的mx
		
		ll m3=min(mid-x+1,tr[p<<1].r[1]); //左半个区间的最大后缀 
		ll m4=min(y-mid,tr[p<<1|1].l[1]); //右半个区间的最大前缀 
		
		return max(max(m1,m2),m3+m4);
	}
	
	pushup(p,l,r);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	build(1,1,n);
	
	cin>>m;
	while(m--)
	{
		ll q,l,r;
		cin>>q>>l>>r;
		
		if(q==1)
		{
			update(1,1,n,l,r);
		}
		else
		{
			cout<<query(1,1,n,l,r)<<"\n";
		}
	}
	
	
	return 0;
}

---

撒花！