HDU 3397 区间覆盖，颠倒，合并（好题）

http://acm.hust.edu.cn/vjudge/problem/14689

三个操作

[a,b]覆盖为0
[a,b]覆盖为1
[a,b]颠倒每项

两个查询

[a,b]间1数量
[a,b]间最长连续1数量

其实是区间覆盖，区间颠倒和区间合并的结合，可以先看这几道题

区间合并：http://www.cnblogs.com/qlky/p/5745065.html

区间更新（两种更新方式）：http://www.cnblogs.com/qlky/p/5737676.html

可以分为两项做：

1的数量很简单，用len[]保存每个区间数量即可

[a,b]区间内最长连续其实之前没做过，具体做法是：

在区间合并的基础上，在query时取左子树，右子树以及min(mid-L+1,rsum[ls])+min(R-mid,lsum[rs])的最小值

这里的min(mid-L+1,rsum[ls])+min(R-mid,lsum[rs])其实就是左子树的右端和右子树左端结合，前面那项是为了限定左右的最大值，因为要在选定的区间内找连续值

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!
")
#define MAXN 100000+5
#define MAX(a,b) a>b?a:b
#define blank pf("
")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f

#define ls (rt<<1)
#define rs (rt<<1|1)

int n,m;

int col[MAXN<<3],a[MAXN<<3],len[MAXN<<3];

int sum[MAXN<<3],lsum[MAXN<<3],rsum[MAXN<<3],mz[MAXN<<3],lz[MAXN<<3],rz[MAXN<<3];


void cg(int &a,int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void FXOR(int rt,int k)
{
    //pf("xor%d %d %d %d t%d %d %d
",rt,sum[rt],lsum[rt],rsum[rt],mz[rt],lz[rt],rz[rt]);
    //统计1数量
    len[rt] = k-len[rt];

    //最长连续1
    cg(sum[rt],mz[rt]);
    cg(lsum[rt],lz[rt]);
    cg(rsum[rt],rz[rt]);
    //pf("xor%d %d %d %d t%d %d %d
",rt,sum[rt],lsum[rt],rsum[rt],mz[rt],lz[rt],rz[rt]);
    if(a[rt]!= -1)
    {
        a[rt]^=1;
    }
    else col[rt]^=1;
}

void PushDown(int rt,int l,int r)
{
    if(l==r) return;
    int mid = (l+r)>>1;
    if(a[rt]!=-1)
    {
        //统计1数量
        a[ls] = a[rt]?a[rt]:0;
        a[rs] = a[rt]?a[rt]:0;
        len[rs] = a[rt]?(r-mid):0;
        len[ls] = a[rt]?(mid-l+1):0;
        //最长连续1
        sum[rs] = lsum[rs] = rsum[rs] = a[rt]?(r-mid):0;
        sum[ls] = lsum[ls] = rsum[ls] = a[rt]?(mid-l+1):0;
        mz[rs] = lz[rs] = rz[rs] = a[rt]?0:(r-mid);
        mz[ls] = lz[ls] = rz[ls] = a[rt]?0:(mid-l+1);

        col[rt] = 0;
        a[rt] = -1;
    }
    if(col[rt])
    {
        if(l!=r)
        {
            FXOR(ls,mid-l+1);
            FXOR(rs,r-mid);
        }
        col[rt] = 0;
    }
}

void PushUp(int rt,int k)
{
    if(k==1) return;
    //最长连续1
    lsum[rt] = lsum[ls];
    lz[rt] = lz[ls];
    rsum[rt] = rsum[rs];
    rz[rt] = rz[rs];
    if(lsum[rt]==k-(k>>1)) lsum[rt]+=lsum[rs];
    if(rsum[rt]==k>>1) rsum[rt]+=rsum[ls];
    if(lz[rt]==k-(k>>1)) lz[rt]+=lz[rs];
    if(rz[rt]==k>>1) rz[rt]+=rz[ls];
    sum[rt] = max(lsum[rs]+rsum[ls],max(sum[rs],sum[ls]));
    mz[rt] = max(lz[rs]+rz[ls],max(mz[rs],mz[ls]));
    //统计1数量
    len[rt] = len[rs]+len[ls];
}

void build(int l,int r,int rt)
{
    a[rt] = -1;
    sum[rt] = lsum[rt] = rsum[rt] = len[rt] = col[rt] = 0;
    mz[rt] = lz[rt] = rz[rt] = r-l+1;
    if(l==r) return;
    int mid = (l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
}

void update(int val,int L,int R,int l,int r,int rt)
{
    if(L<=l && r<=R)
    {
        if(val==0)
        {
            //统计1数量
            len[rt] = a[rt] = col[rt] = 0;

            //统计最长连续1
            sum[rt] = rsum[rt] = lsum[rt] = 0;
            mz[rt] = rz[rt] = lz[rt] = r-l+1;
        }
        else if(val==1)
        {
            //统计1数量
            len[rt] = r-l+1;
            a[rt] = 1;
            col[rt] = 0;

            //统计最长连续1
            sum[rt] = rsum[rt] = lsum[rt] = r-l+1;
            mz[rt] = rz[rt] = lz[rt] = 0;
        }
        else
        {
            FXOR(rt,r-l+1);
        }
        return;
    }
    PushDown(rt,l,r);
    int mid = (l+r)>>1;
    if(L <= mid) update(val,L,R,l,mid,ls);
    if(R > mid) update(val,L,R,mid+1,r,rs);
    PushUp(rt,r-l+1);
}

LL ans = 0;

//统计1数量
void query(int L,int R,int l,int r,int rt)
{
    //pf("%d %d %d %d
",L,R,l,r);
    if(L <= l && r <= R)
    {
        ans+=len[rt];
        return;
    }
    PushDown(rt,l,r);
    int mid = (l+r)>>1;
    if(L<=mid) query(L,R,l,mid,ls);
    if(R>mid) query(L,R,mid+1,r,rs);
}

//最长连续1
int query2(int L,int R,int l,int r,int rt)
{
    //pf("%d %d %d %d
",L,R,l,r);
    if(L <= l && r <= R)
    {
        return sum[rt];
    }
    PushDown(rt,l,r);
    int res = 0;
    int mid = (l+r)>>1;
    if(L<=mid)
    {
        int tmp = query2(L,R,l,mid,ls);
        res = max(tmp,res);
    }
    if(R>mid)
    {
        int tmp = query2(L,R,mid+1,r,rs);
        res = max(tmp,res);
    }
    res = max(res,min(mid-L+1,rsum[ls])+min(R-mid,lsum[rs]));
    return res;
}

int main()
{
    int n,i,j,t,kase=1;
    sf("%d",&t);
    while(t--)
    {
        sf("%d%d",&n,&m);
        build(1,n,1);
        for(i=1;i<=n;i++)
        {
            int tmp;
            sf("%d",&tmp);
            update(tmp,i,i,1,n,1);
        }
        //for(i=1;i<=18;i++) pf("t%d %d %d %d
",i,sum[i],lsum[i],rsum[i]);
        //for(i=1;i<=18;i++) pf("t%d %d %d %d
",i,mz[i],lz[i],rz[i]);
        for(i=1;i<=m;i++)
        {
            int tmp,c,d;
            sf("%d%d%d",&tmp,&c,&d);
            if(tmp==0) update(0,c+1,d+1,1,n,1);
            else if (tmp==1) update(1,c+1,d+1,1,n,1);
            else if(tmp==2) update(2,c+1,d+1,1,n,1);
            else if(tmp==3)
            {
                ans = 0;
                query(c+1,d+1,1,n,1);
                pf("%I64d
",ans);
            }
            else
            {
                pf("%d
",query2(c+1,d+1,1,n,1));
            }
            //for(j=1;j<=18;j++) pf("t%d %d %d %d t%d %d
",j,sum[j],lsum[j],rsum[j],a[j],col[j]);
            //for(j=1;j<=18;j++) pf("tt%d %d %d %d
",j,mz[j],lz[j],rz[j]);
        }
    }
    return 0;
}
/*
1
10 1000
0 0 0 1 1 0 1 0 1 1
3 0 0
3 1 1
3 2 2
3 3 3
3 4 4
3 5 5
3 6 6
3 7 7
3 8 8
3 9 9
3 0 0
3 0 1
3 0 2
3 0 3
3 0 4
3 0 5
3 0 6
3 0 7
3 0 8
3 0 9
*/