HDU-3911-线段树区间合并-延迟标记
!
题意
给定区间01，然后可以把区间0变1，1变0，然后求最大连续1的长度
题解
正常的维护01区间，用lazy 来表示反转，多维护一个最大0的左连续，右连续，连续最大
然后反转的时候，直接swap 一下就可以
但是有一个坑点，就是查找区间最大连续1的时候，如果是包含你要的区间
那就直接返回这个区间最大的值，如果是这个区间完全左边和右边的时候也直接递归就可以
但是当在这个区间某一部分的时候，会有问题
比如 1-10 你找 2-8 你肯定要找到 1-5 和 6-10 对吧
但是，你分开区间的时候，你会把 1-5和6-10 区间连续的部分分开
所以，一定要考虑中间分开的连续区间
第一种就是完全包含直接返回，第二种完全右边和左边直接递归
第三种中间某部分分开的，比如 1-10，你找 2-8，1-10肯定没有了，
你要找1-5 和 6-10 里面的对吧，但是你分开的时候 1-5的右区间和6-10左区间连续被分开了
所以你要讨论一下 而且还要注意大小
因为 假设 1-10 找2-8 假设1-5 右连续贯穿 这个时候就比2大了 同理右儿子左连续也得比较一下
具体的看代码就行，主要来说就是你在往下递归这个树的时候，在分开的时候多考虑一下中间的情况
AC代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100005
struct node
{
int l,r;
int ls,rs,sum;
int lazy;
int ls2,rs2,sum2;
};
node shu[N<<2];
int a[N];
void pushup(int rt)
{
shu[rt].ls = shu[rt<<1].ls;
shu[rt].rs = shu[rt<<1|1].rs;
if(shu[rt<<1].ls==(shu[rt<<1].r - shu[rt<<1].l + 1))
{
shu[rt].ls += shu[rt<<1|1].ls;
}
if(shu[rt<<1|1].rs==(shu[rt<<1|1].r - shu[rt<<1|1].l + 1))
{
shu[rt].rs += shu[rt<<1].rs;
}
shu[rt].sum = max(max(shu[rt<<1].sum,shu[rt<<1|1].sum),shu[rt<<1].rs+shu[rt<<1|1].ls);
shu[rt].ls2 = shu[rt<<1].ls2;
shu[rt].rs2 = shu[rt<<1|1].rs2;
if(shu[rt<<1].ls2==(shu[rt<<1].r - shu[rt<<1].l + 1))
{
shu[rt].ls2 += shu[rt<<1|1].ls2;
}
if(shu[rt<<1|1].rs2==(shu[rt<<1|1].r - shu[rt<<1|1].l + 1))
{
shu[rt].rs2 += shu[rt<<1].rs2;
}
shu[rt].sum2 = max(max(shu[rt<<1].sum2,shu[rt<<1|1].sum2),shu[rt<<1].rs2+shu[rt<<1|1].ls2);
}
void build(int rt,int l,int r)
{
shu[rt].l = l,shu[rt].r = r;
shu[rt].lazy = 0;
if(l==r)
{
if(a[l])
{
shu[rt].ls = shu[rt].rs = shu[rt].sum = 1;
shu[rt].ls2 = shu[rt].rs2 = shu[rt].sum2 = 0;
}
else
{
shu[rt].ls = shu[rt].rs = shu[rt].sum = 0;
shu[rt].ls2 = shu[rt].rs2 = shu[rt].sum2 = 1;
}
return;
}
int mid = (l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void pushdown(int rt)
{
if(shu[rt].lazy)
{
swap(shu[rt<<1].ls,shu[rt<<1].ls2);
swap(shu[rt<<1].rs,shu[rt<<1].rs2);
swap(shu[rt<<1].sum,shu[rt<<1].sum2);
swap(shu[rt<<1|1].ls,shu[rt<<1|1].ls2);
swap(shu[rt<<1|1].rs,shu[rt<<1|1].rs2);
swap(shu[rt<<1|1].sum,shu[rt<<1|1].sum2);
shu[rt<<1].lazy ^= shu[rt].lazy;
shu[rt<<1|1].lazy ^= shu[rt].lazy;
shu[rt].lazy ^= 1;
}
}
void update(int rt,int l,int r)
{
int L = shu[rt].l , R = shu[rt].r;
if(l<=L&&R<=r)
{
swap(shu[rt].ls,shu[rt].ls2);
swap(shu[rt].rs,shu[rt].rs2);
swap(shu[rt].sum,shu[rt].sum2);
shu[rt].lazy ^=1;
}
else
{
pushdown(rt);
int mid = (L+R)>>1;
if(l<=mid) update(rt<<1,l,r);
if(mid<r) update(rt<<1|1,l,r);
pushup(rt);
}
}
int Find(int rt,int l,int r)
{
int L = shu[rt].l, R = shu[rt].r;
if(L==l&&R==r)
{
return shu[rt].sum;
}
pushdown(rt);
int ans = 0;
int mid = (L+R)>>1;
if(r<=mid)
{
ans = Find(rt<<1,l,r);
}
else if(l>mid)
{
ans = Find(rt<<1|1,l,r);
}
else
{
int v1 = Find(rt<<1,l,mid);
int v2 = Find(rt<<1|1,mid+1,r);
int v3 = min(shu[rt<<1].rs, mid-l+1) + min(shu[rt<<1|1].ls,r-mid-1+1);
int v4 = max(v1,v2);
ans = max(v3,v4);
}
pushup(rt);
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
memset(shu,0,sizeof(shu));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,1,n);
int m;
scanf("%d",&m);
while(m--)
{
int x,l,r;
scanf("%d%d%d",&x,&l,&r);
if(x==0)
{
printf("%d\n",Find(1,l,r));
}
else if(x==1)
{
update(1,l,r);
}
}
}
}