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("!\n")

#define MAXN 100000+5

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#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<<],a[MAXN<<],len[MAXN<<];

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

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\n",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\n",rt,sum[rt],lsum[rt],rsum[rt],mz[rt],lz[rt],rz[rt]);

    if(a[rt]!= -)

    {

        a[rt]^=;

    }

    else col[rt]^=;

}

void PushDown(int rt,int l,int r)

{

    if(l==r) return;

    int mid = (l+r)>>;

    if(a[rt]!=-)

    {

        //统计1数量

        a[ls] = a[rt]?a[rt]:;

        a[rs] = a[rt]?a[rt]:;

        len[rs] = a[rt]?(r-mid):;

        len[ls] = a[rt]?(mid-l+):;

        //最长连续1

        sum[rs] = lsum[rs] = rsum[rs] = a[rt]?(r-mid):;

        sum[ls] = lsum[ls] = rsum[ls] = a[rt]?(mid-l+):;

        mz[rs] = lz[rs] = rz[rs] = a[rt]?:(r-mid);

        mz[ls] = lz[ls] = rz[ls] = a[rt]?:(mid-l+);

        col[rt] = ;

        a[rt] = -;

    }

    if(col[rt])

    {

        if(l!=r)

        {

            FXOR(ls,mid-l+);

            FXOR(rs,r-mid);

        }

        col[rt] = ;

    }

}

void PushUp(int rt,int k)

{

    if(k==) return;

    //最长连续1

    lsum[rt] = lsum[ls];

    lz[rt] = lz[ls];

    rsum[rt] = rsum[rs];

    rz[rt] = rz[rs];

    if(lsum[rt]==k-(k>>)) lsum[rt]+=lsum[rs];

    if(rsum[rt]==k>>) rsum[rt]+=rsum[ls];

    if(lz[rt]==k-(k>>)) lz[rt]+=lz[rs];

    if(rz[rt]==k>>) 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] = -;

    sum[rt] = lsum[rt] = rsum[rt] = len[rt] = col[rt] = ;

    mz[rt] = lz[rt] = rz[rt] = r-l+;

    if(l==r) return;

    int mid = (l+r)>>;

    build(l,mid,ls);

    build(mid+,r,rs);

}

void update(int val,int L,int R,int l,int r,int rt)

{

    if(L<=l && r<=R)

    {

        if(val==)

        {

            //统计1数量

            len[rt] = a[rt] = col[rt] = ;

            //统计最长连续1

            sum[rt] = rsum[rt] = lsum[rt] = ;

            mz[rt] = rz[rt] = lz[rt] = r-l+;

        }

        else if(val==)

        {

            //统计1数量

            len[rt] = r-l+;

            a[rt] = ;

            col[rt] = ;

            //统计最长连续1

            sum[rt] = rsum[rt] = lsum[rt] = r-l+;

            mz[rt] = rz[rt] = lz[rt] = ;

        }

        else

        {

            FXOR(rt,r-l+);

        }

        return;

    }

    PushDown(rt,l,r);

    int mid = (l+r)>>;

    if(L <= mid) update(val,L,R,l,mid,ls);

    if(R > mid) update(val,L,R,mid+,r,rs);

    PushUp(rt,r-l+);

}

LL ans = ;

//统计1数量

void query(int L,int R,int l,int r,int rt)

{

    //pf("%d %d %d %d\n",L,R,l,r);

    if(L <= l && r <= R)

    {

        ans+=len[rt];

        return;

    }

    PushDown(rt,l,r);

    int mid = (l+r)>>;

    if(L<=mid) query(L,R,l,mid,ls);

    if(R>mid) query(L,R,mid+,r,rs);

}

//最长连续1

int query2(int L,int R,int l,int r,int rt)

{

    //pf("%d %d %d %d\n",L,R,l,r);

    if(L <= l && r <= R)

    {

        return sum[rt];

    }

    PushDown(rt,l,r);

    int res = ;

    int mid = (l+r)>>;

    if(L<=mid)

    {

        int tmp = query2(L,R,l,mid,ls);

        res = max(tmp,res);

    }

    if(R>mid)

    {

        int tmp = query2(L,R,mid+,r,rs);

        res = max(tmp,res);

    }

    res = max(res,min(mid-L+,rsum[ls])+min(R-mid,lsum[rs]));

    return res;

}

int main()

{

    int n,i,j,t,kase=;

    sf("%d",&t);

    while(t--)

    {

        sf("%d%d",&n,&m);

        build(,n,);

        for(i=;i<=n;i++)

        {

            int tmp;

            sf("%d",&tmp);

            update(tmp,i,i,,n,);

        }

        //for(i=1;i<=18;i++) pf("t%d %d %d %d\n",i,sum[i],lsum[i],rsum[i]);

        //for(i=1;i<=18;i++) pf("t%d %d %d %d\n",i,mz[i],lz[i],rz[i]);

        for(i=;i<=m;i++)

        {

            int tmp,c,d;

            sf("%d%d%d",&tmp,&c,&d);

            if(tmp==) update(,c+,d+,,n,);

            else if (tmp==) update(,c+,d+,,n,);

            else if(tmp==) update(,c+,d+,,n,);

            else if(tmp==)

            {

                ans = ;

                query(c+,d+,,n,);

                pf("%I64d\n",ans);

            }

            else

            {

                pf("%d\n",query2(c+,d+,,n,));

            }

            //for(j=1;j<=18;j++) pf("t%d %d %d %d t%d %d\n",j,sum[j],lsum[j],rsum[j],a[j],col[j]);

            //for(j=1;j<=18;j++) pf("tt%d %d %d %d\n",j,mz[j],lz[j],rz[j]);

        }

    }

    return ;

}

/*

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

*/

巴特西

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

最新文章

热门文章