參考 http://dnizna.javaeye.com/blog/657622 的 寫法
  /**//*
 題意：長度為N的01串，Q個操作
0 a b 將[a,b]置0
1 a b 將[a,b]置1
2 a b 將[a,b]內(nèi)的數(shù)翻轉，0->1 1->0
3 a b 查詢[a,b]內(nèi)1的個數(shù)
4 a b 查詢[a,b]內(nèi)最多的連續(xù)1個數(shù)
維護max1,maxL1,maxR1 最多連續(xù)1的個數(shù)，左邊最多連續(xù)1的個數(shù)，右邊最多連續(xù)1的個數(shù)
需要延遲標記 set rev
set = 1 表示置為1
set = 0 表示置為0
set = -1 表示沒有置數(shù)
rev = 1表示需要翻轉
所以在需要修改時，遇到整段修改的，將該段的值更新為正確的
如set 1 的話 sum = right - left +1
然后對于其兒子的，不用更新！直接在該段標記set = 1 表示以后孩子需要更新，但該段已經(jīng)是正確的值！！！
標記的做法主要就是上面說的了，某一段是正確的，但標記其兒子等都需要修改
每次遇到一條線段時，push_down() ，這樣子實現(xiàn)了延遲更新了
如果set = 1,rev = 1這樣子并不表明是先set，還是先reverse，就這里的細節(jié)了！！
但如果要set的話，必定不需再reverse了
所以在某一段，如果其需要set，更新孩子，將該標記傳給孩子，表明孩子的孩子以后需要更新
同時，將孩子的rev = 0
即： rev + set -> set
set + rev -> set + rev
所以push_down()那里的處理順序是：
if(set)
if(rev)
兩者是并列的！！
考慮例子：
[0 4]
[0 2]
先將[0,2]標記(set or rev)，接下來是標記[0,4]，上面的覆蓋下面了
所以為set的話，[0,2]的rev置為0了 rev的話，就傳下去
所以push_down()的if 是并列的
 */
 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
int x[MAXN];
struct Node
 {
int max0,maxL0,maxR0;
int max1,maxL1,maxR1;
int sum,set,rev;
};
struct SegTree
{
Node nodes[MAXN*3];
void update(int p,int left,int right)
  {
if(left == right)return;
nodes[p].sum = nodes[2*p].sum + nodes[2*p+1].sum;
int mid = (left+right)>>1;
nodes[p].maxL0 = nodes[2*p].maxL0;
if(nodes[p].maxL0 == mid-left+1)nodes[p].maxL0 += nodes[2*p+1].maxL0;
nodes[p].maxR0 = nodes[2*p+1].maxR0;
if(nodes[p].maxR0 == right-mid)nodes[p].maxR0 += nodes[2*p].maxR0;
nodes[p].max0 = max(nodes[2*p].max0,nodes[2*p+1].max0);
nodes[p].max0 = max(nodes[p].max0,nodes[2*p].maxR0+nodes[2*p+1].maxL0);
nodes[p].maxL1 = nodes[2*p].maxL1;
if(nodes[p].maxL1 == mid-left+1)nodes[p].maxL1 += nodes[2*p+1].maxL1;
nodes[p].maxR1 = nodes[2*p+1].maxR1;
if(nodes[p].maxR1 == right-mid)nodes[p].maxR1 += nodes[2*p].maxR1;
nodes[p].max1 = max(nodes[2*p].max1,nodes[2*p+1].max1);
nodes[p].max1 = max(nodes[p].max1,nodes[2*p].maxR1+nodes[2*p+1].maxL1);
 }
void push_down(int p,int left,int right)
{
if(left == right)return;
int mid = (left+right)>>1;
//set 與 rev 是并列的！！！
if(nodes[p].set != -1)
{
int val = nodes[p].set;
nodes[p].set = -1;
nodes[2*p].set = nodes[2*p+1].set = val;
nodes[2*p].rev = nodes[2*p+1].rev = 0;//將孩子的rev置為0
nodes[2*p].sum = val==1?mid-left+1:0;
nodes[2*p].max0 = nodes[2*p].maxL0 = nodes[2*p].maxR0 = val==0?mid-left+1:0;
nodes[2*p].max1 = nodes[2*p].maxL1 = nodes[2*p].maxR1 = val==1?mid-left+1:0;
nodes[2*p+1].sum = val==1?right-mid:0;
nodes[2*p+1].max0 = nodes[2*p+1].maxL0 = nodes[2*p+1].maxR0 = val==0?right-mid:0;
nodes[2*p+1].max1 = nodes[2*p+1].maxL1 = nodes[2*p+1].maxR1 = val==1?right-mid:0;
}
if(nodes[p].rev)
{
nodes[p].rev = false;
nodes[2*p].rev ^= 1;//這里是翻轉！！！
nodes[2*p+1].rev ^= 1;
nodes[2*p].sum = mid-left+1 - nodes[2*p].sum;
swap(nodes[2*p].max0,nodes[2*p].max1);
swap(nodes[2*p].maxL0,nodes[2*p].maxL1);
swap(nodes[2*p].maxR0,nodes[2*p].maxR1);
nodes[2*p+1].sum = right - mid - nodes[2*p+1].sum;
swap(nodes[2*p+1].max0,nodes[2*p+1].max1);
swap(nodes[2*p+1].maxL0,nodes[2*p+1].maxL1);
swap(nodes[2*p+1].maxR0,nodes[2*p+1].maxR1);
}
}
void build(int p,int left,int right)
{
nodes[p].set = -1;
nodes[p].rev = 0;
if(left == right)
{
nodes[p].sum = x[left];
nodes[p].max0 = nodes[p].maxL0 = nodes[p].maxR0 = (x[left]==0);
nodes[p].max1 = nodes[p].maxL1 = nodes[p].maxR1 = (x[left]==1);
return;
}
int mid = (left+right)>>1;
build(2*p,left,mid);
build(2*p+1,mid+1,right);
update(p,left,right);
}
void change(int p,int left,int right,int l,int r,int op)
{
push_down(p,left,right);
if(l<=left && right<=r)
{
if(op == 2)
{
nodes[p].rev = true;
nodes[p].sum = right - left + 1 - nodes[p].sum;
swap(nodes[p].max0,nodes[p].max1);
swap(nodes[p].maxL0,nodes[p].maxL1);
swap(nodes[p].maxR0,nodes[p].maxR1);
}
else
{
nodes[p].set = op;
nodes[p].sum = op==1?right-left+1:0;
nodes[p].max0 = nodes[p].maxL0 = nodes[p].maxR0 = op==0?right-left+1:0;
nodes[p].max1 = nodes[p].maxL1 = nodes[p].maxR1 = op==1?right-left+1:0;
}
return;
}
int mid = (left+right) >>1;
if(l>mid)change(2*p+1,mid+1,right,l,r,op);
else if(r<=mid)change(2*p,left,mid,l,r,op);
else
{
change(2*p,left,mid,l,mid,op);
change(2*p+1,mid+1,right,mid+1,r,op);
}
update(p,left,right);
}
int query(int p,int left,int right,int l,int r,int op)
{
push_down(p,left,right);
if(l<=left && right<=r)
{
if(op==3)return nodes[p].sum;
return nodes[p].max1;
}
int mid = (left+right)>>1;
if(l>mid)return query(2*p+1,mid+1,right,l,r,op);
if(r<=mid)return query(2*p,left,mid,l,r,op);
if(op==3)return query(2*p,left,mid,l,mid,op)+query(2*p+1,mid+1,right,mid+1,r,op);
int ans = max(query(2*p,left,mid,l,mid,op),query(2*p+1,mid+1,right,mid+1,r,op));
int L = min(nodes[2*p].maxR1,mid+1-l);
int R = min(nodes[2*p+1].maxL1,r-mid);
ans = max(ans,L+R);
return ans;
}
};
SegTree segTree;
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in","r",stdin);
#endif
int T;
for(scanf("%d",&T);T--;)
{
int N,Q;
int q,a,b;
scanf("%d%d",&N,&Q);
for(int i=0;i<N;i++)
scanf("%d",&x[i]);
segTree.build(1,0,N-1);
for(int i=0;i<Q;i++)
{
scanf("%d%d%d",&q,&a,&b);
if(q<=2)segTree.change(1,0,N-1,a,b,q);
else printf("%d\n",segTree.query(1,0,N-1,a,b,q));
}
}
return 0;
}
|