HDU3991：Black and White

浅谈树状数组与线段树：https://www.cnblogs.com/AKMer/p/9946944.html

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3911

用线段树维护六个信息，分别是区间最长子段，最左边连续的最长段，最右边连续的最长段，然后分\(0\)，\(1\)分别处理出来。询问的时候因为会先访问最左边的段，然后依次往右走，所以开一个全局变量存上一段最右一段\(1\)有多长，然后和当前段合并起来更新答案就行。

时间复杂度：\(O(mlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e5+5;

int a[maxn];

int n,m,ans,mx;

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct tree_node {

    int mx[2],lft[2],rgt[2];

};

struct segment_tree {

    bool rev[maxn<<2];

    tree_node tree[maxn<<2];

    void updata(int p,int l,int r) {

        int mid=(l+r)>>1;

        for(int i=0;i<2;i++) {

            tree[p].mx[i]=max(tree[p<<1].rgt[i]+tree[p<<1|1].lft[i],max(tree[p<<1].mx[i],tree[p<<1|1].mx[i]));

            if(tree[p<<1].lft[i]==mid-l+1)tree[p].lft[i]=tree[p<<1].lft[i]+tree[p<<1|1].lft[i];

            else tree[p].lft[i]=tree[p<<1].lft[i];

            if(tree[p<<1|1].rgt[i]==r-mid)tree[p].rgt[i]=tree[p<<1].rgt[i]+tree[p<<1|1].rgt[i];

            else tree[p].rgt[i]=tree[p<<1|1].rgt[i];

        }

    }

    void add_tag(int p) {

        rev[p]^=1;

        swap(tree[p].mx[0],tree[p].mx[1]);

        swap(tree[p].lft[0],tree[p].lft[1]);

        swap(tree[p].rgt[0],tree[p].rgt[1]);

    }

    void push_down(int p) {

        if(rev[p]) {

            add_tag(p<<1);

            add_tag(p<<1|1);

            rev[p]=0;

        }

    }

    void build(int p,int l,int r) {

        rev[p]=0;

        for(int i=0;i<2;i++)

            tree[p].mx[i]=tree[p].lft[i]=tree[p].rgt[i]=0;//多组数据要记得清空

        if(l==r) {

            tree[p].mx[a[l]]=1;

            tree[p].lft[a[l]]=1;

            tree[p].rgt[a[l]]=1;

            return;

        }

        int mid=(l+r)>>1;

        build(p<<1,l,mid);

        build(p<<1|1,mid+1,r);

        updata(p,l,r);

    }

    void rever(int p,int l,int r,int L,int R) {

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

            add_tag(p);

            return;

        }

        int mid=(l+r)>>1;push_down(p);

        if(L<=mid)rever(p<<1,l,mid,L,R);

        if(R>mid)rever(p<<1|1,mid+1,r,L,R);

        updata(p,l,r);

    }

    void query(int p,int l,int r,int L,int R) {

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

            ans+=tree[p].lft[1];

            mx=max(mx,max(tree[p].mx[1],ans));

            if(tree[p].lft[1]!=r-l+1)ans=tree[p].rgt[1];

            return;

        }

        int mid=(l+r)>>1;push_down(p);

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

        if(R>mid)query(p<<1|1,mid+1,r,L,R);

    }

}T;

int main() {

    while(~scanf("%d",&n)) {

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

            a[i]=read();

        T.build(1,1,n);m=read();

        for(int i=1;i<=m;i++) {

            int opt=read(),l=read(),r=read();

            if(opt==1)T.rever(1,1,n,l,r);

            else {

                ans=mx=0;

                T.query(1,1,n,l,r);

                printf("%d\n",mx);

            }

        }

    }

    return 0;

}