线段树 poj3225

U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换

因为普通的线段树实际处理的并非真正的区间，而是一系列点，相当于处理一个向量。这个问题需要处理的是真正的区间，所以应该有一个主导思想就是，把区间点化！不知哪位大牛搞了一个倍增区间出来，实在佩服！对于待处理区间[a,b](暂时不考虑开闭)，对其边界均乘2。若区间左开则对左界值+1，若区间右开，则对右界-1！

如：[2,3]会倍增为[4,6]，[2,3)会倍增为[4,5]，（2,3]会倍增为[5,6]，(2,3)将倍增为[5,5]，我们这时可以看到，对于普通线段树无法处理的线段如(x,x+1)将被点化为[2*x+1,2*x+1]！这个问题得到比较完美的解决

最后把查找出来的区间逆向倍增操作一下，就可以得到实际的区间以及起开闭情况！

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

#define MAXN1 65545<<1

#define MAXN  65535<<1

int x[MAXN<<],col[MAXN<<];

void FXOR(int a)

{

    if(x[a]!=-)

        x[a]^=;

    else

        col[a]^=;

}

void push_down(int a)

{

    if(x[a]!=-)

    {

        x[a<<]=x[a<<|]=x[a];

        col[a<<]=col[a<<|]=;

        x[a]=-;

    }

    if(col[a])

    {

        FXOR(a<<);

        FXOR(a<<|);

        col[a]=;

    }

}

void update(char val,int l,int r,int a1,int b1,int a)

{

    if(l>=a1&&b1>=r)

    {

        if(val=='U')

        {

            x[a]=;

            col[a]=;

        }

        else if(val=='D')

        {

            x[a]=;

            col[a]=;

        }

        else if(val=='S'||val=='C')

            FXOR(a);

        return ;

    }

    push_down(a);

    int mid=(l+r)>>;

    if(a1<=mid)

        update(val,l,mid,a1,b1,a<<);

    else if(val=='I'||val=='C')

        x[a<<]=col[a<<]=;

    if(b1>mid)

        update(val,mid+,r,a1,b1,a<<|);

    else if(val=='I'||val=='C')

        x[a<<|]=col[a<<|]=;

}

bool vis[MAXN1];

void Query(int l,int r,int a)

{

    if(x[a]==)

    {

        for(int i=l;i<=r;i++)

            vis[i]=;

        return ;

    }

    else if(x[a]==)

        return ;

    if(l==r)

        return ;

    push_down(a);

    int mid=(l+r)>>;

    Query(l,mid,a<<);

    Query(mid+,r,a<<|);

}

int main()

{

    x[]=col[]=;

    char a,a1,a2,b;

    int l,r;

    while(scanf("%c %c%d,%d%c%c",&a,&a1,&l,&r,&a2,&b)!=EOF)

    {

        l<<=;

        r<<=;

        if(a1=='(')

            l++;

        if(a2==')')

            r--;

        if(l>r)

            continue;

        update(a,,MAXN,l,r,);

    }

    Query(,MAXN,);

    int s=-,e;

    bool flag=;

    for(int i=;i<=MAXN;i++)

    {

        if(vis[i])

        {

            if(s==-)

                s=i;

            e=i;

        }

        else

        {

            if(s!=-)

            {

                if(flag)printf(" ");

                printf("%c%d,%d%c",s&?'(':'[',s>>,(e+)>>,e&?')':']');

                s=-;

                flag=;

            }

        }

    }

    if(!flag)

        printf("empty set");

    return ;

}

巴特西

线段树 poj3225

最新文章

热门文章