题目链接：Click here~~
题意：
很给力的线段树题，感觉对帮助理解线段树十分有帮助。写了 200 行，debug了 2 小时。好爽。
有一个数列，然后5种操作：
1、将 [a,b] 中所有数变成0。
2、将 [a,b] 中所有数变成1。
3、将 [a,b] 中所有数取反。
4、询问 [a,b] 中 1 的个数。
5、询问 [a,b] 中最长连续 1 的长度。
解题思路：
一眼过去肯定是线段树啊。考虑存些什么值才可以使问题能解。
首先，sum of 1 是肯定要存的。而且，它可以不依赖其他信息就在 O(1) 使区间的 sum 得到更新。
然后，最长连续 1 长度也是要存的。但是，考虑区间合并的时候，子区间的值并不能直接合并到父区间。（ max{ 子区间 } ≠ 父区间 ）
所以，我们还要记录每个区间从 左/右 开始的最长连续 1 的长度，那样，就可以解决区间合并的问题了。
等下，更新怎么办？操作 1、2 都好说，但是 3 怎么办？
没错，再相似的记录下最长连续 0。对于操作3，等价于于 1 和 0 的属性互换。
再给前三个操作分别弄个懒惰标记就行了，哈哈。
细节：
由于有两个标记，考虑标记的先后顺序会对结果产生影响。
怎么处理这个问题呢？
当执行操作 1、2 的时候，把操作 3 的标记擦除。
然后如果某个节点同时有 2 个标记，说明是先进行的操作 1、2 ，然后进行的操作 3 。
附代码。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define lson u<<1
#define rson u<<1|1
const int N = 1e5+5;
int cmd;
struct SegTree
{
int l,r;
int sum,lmax[2],rmax[2],max[2],to;
bool xxor;
inline int len(){
return r-l;
}
inline int mid(){
return l+r >> 1;
}
}T[N<<2];
void push_up(int u)
{
T[u].sum = T[lson].sum + T[rson].sum;
for(int i=0;i<=1;i++)
{
T[u].max[i] = max(T[lson].rmax[i]+T[rson].lmax[i] , max(T[lson].max[i],T[rson].max[i]));
if(T[lson].lmax[i] == T[lson].len())
T[u].lmax[i] = T[lson].lmax[i] + T[rson].lmax[i];
else
T[u].lmax[i] = T[lson].lmax[i];
if(T[rson].rmax[i] == T[rson].len())
T[u].rmax[i] = T[lson].rmax[i] + T[rson].rmax[i];
else
T[u].rmax[i] = T[rson].rmax[i];
}
}
void changeX(int u)
{
T[u].sum = T[u].len() - T[u].sum;
swap(T[u].max[0],T[u].max[1]);
swap(T[u].lmax[0],T[u].lmax[1]);
swap(T[u].rmax[0],T[u].rmax[1]);
}
void changeT(int u)
{
int to = T[u].to;
T[u].sum = to ? T[u].len() : 0;
T[u].max[to] = T[u].lmax[to] = T[u].rmax[to] = T[u].len();
T[u].max[to^1] = T[u].lmax[to^1] = T[u].rmax[to^1] = 0;
}
void push_down(int u)
{
if(T[u].to != -1)
{
T[lson].to = T[rson].to = T[u].to;
T[lson].xxor = T[rson].xxor = false;
changeT(lson);
changeT(rson);
T[u].to = -1;
}
if(T[u].xxor)
{
T[lson].xxor ^= 1;
T[rson].xxor ^= 1;
changeX(lson);
changeX(rson);
T[u].xxor = false;
}
}
void debug(int u)
{
printf("***[%d,%d)***\n",T[u].l,T[u].r);
printf(" sum=> %d\n",T[u].sum);
for(int i=0;i<=1;i++)
{
printf("\t lmax[%d]:%d\n",i,T[u].lmax[i]);
printf("\t rmax[%d]:%d\n",i,T[u].rmax[i]);
printf("\t max[%d]:%d\n",i,T[u].max[i]);
}
puts("\n");
}
void build(int u,int l,int r)
{
T[u].l = l , T[u].r = r;
T[u].to = -1;
T[u].xxor = false;
if(l == r-1)
{
int num;
scanf("%d",&num);
T[u].sum = num;
T[u].max[0] = T[u].lmax[0] = T[u].rmax[0] = num ^ 1;
T[u].max[1] = T[u].lmax[1] = T[u].rmax[1] = num & 1;
return ;
}
int m = T[u].mid();
build(lson,l,m);
build(rson,m,r);
push_up(u);
}
void updata(int u,int l,int r)
{
if(l == T[u].l && r == T[u].r)
{
if(cmd == 2)
{
T[u].xxor ^= 1;
changeX(u);
}
else
{
T[u].to = cmd;
T[u].xxor = false;
changeT(u);
}
return ;
}
int m = T[u].mid();
push_down(u);
if(r <= m)
updata(lson,l,r);
else if(l >= m)
updata(rson,l,r);
else
updata(lson,l,m) , updata(rson,m,r);
push_up(u);
}
int queryS(int u,int l,int r)
{
if(l == T[u].l && r == T[u].r)
{
return T[u].sum;
}
int m = T[u].mid();
push_down(u);
if(r <= m)
return queryS(lson,l,r);
else if(l >= m)
return queryS(rson,l,r);
else
return queryS(lson,l,m) + queryS(rson,m,r);
}
int queryM(int u,int l,int r)
{
if(l == T[u].l && r == T[u].r)
{
return T[u].max[1];
}
int m = T[u].mid();
push_down(u);
if(r <= m)
return queryM(lson,l,r);
else if(l >= m)
return queryM(rson,l,r);
else
{
int ans = max(queryM(lson,l,m),queryM(rson,m,r));
ans = max(ans,min(m-l,T[lson].rmax[1])+min(r-m,T[rson].lmax[1]));
return ans;
}
}
int main()
{
//freopen("in.ads","r",stdin);
int z,n,Q;
scanf("%d",&z);
while(z--)
{
scanf("%d%d",&n,&Q);
build(1,1,n+1);
while(Q--)
{
int a,b;
scanf("%d%d%d",&cmd,&a,&b);
++a , ++b;
if(cmd <= 2)
updata(1,a,b+1);
else if(cmd == 3)
printf("%d\n",queryS(1,a,b+1));
else
printf("%d\n",queryM(1,a,b+1));
}
}
return 0;
}