bzoj 3226: [Sdoi2008]校门外的区间

.

题意：集合运算。
题解：线段树。把所有数*2，开区间就可以转化为闭区间。乱搞一下就好了。
代码：（不是一般的恶心。。）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#define pa pair<int,int>
using namespace std;

struct tree
{
    int l,r,lc,rc,cl,cr;//-2:空 -1:杂  
}tr[280010];
int num=0,l,r,s[131074];
bool lt,rt;
char type;
vector<pa>ans;

void print(int i)
{
    printf("%d %d %d %d %d\n",i,tr[i].l,tr[i].r,tr[i].cl,tr[i].cr);
}
bool in()
{
    char s1[4],s2[20];
    if(scanf("%s%s",s1,s2)==EOF)
    return 0;
    type=s1[0];
    l=r=0;
    char* ch=s2;
    lt=*ch=='[';
    ch++;
    while(*ch>='0'&&*ch<='9')
    {
        l=l*10+*ch-'0';
        ch++;
    }
    ch++;
    while(*ch>='0'&&*ch<='9')
    {
        r=r*10+*ch-'0';
        ch++;
    }
    rt=*ch==']';
    return 1;
}
int bt(int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    tr[i].cl=tr[i].cr=-2;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt(l,md);
        tr[i].rc=bt(md+1,r);
    }
    return i;
}
void pushdown(int x)
{
        int lc=tr[x].lc,rc=tr[x].rc,md=tr[x].l+tr[x].r>>1;
    if(tr[x].cl>=0)
    {
        if(tr[x].cr<=md)
        {
            tr[lc].cl=tr[x].cl;
            tr[lc].cr=tr[x].cr;
            tr[rc].cl=tr[rc].cr=-2;
        }
        else if(tr[x].cl>md)
        {
            tr[rc].cl=tr[x].cl;
            tr[rc].cr=tr[x].cr;
            tr[lc].cl=tr[lc].cr=-2;
        }
        else
        {
            tr[lc].cl=tr[x].cl;
            tr[lc].cr=md;
            tr[rc].cl=md+1;
            tr[rc].cr=tr[x].cr;
        }
    }
    if(tr[x].cl==-2)
    tr[lc].cl=tr[lc].cr=tr[rc].cl=tr[rc].cr=-2;
}
void pushup(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc,md=tr[x].l+tr[x].r>>1;
    if(tr[lc].cl==-1||tr[rc].cl==-1||(tr[lc].cr<md&&tr[lc].cr>=0&&tr[rc].cl>=0)||(tr[rc].cl>md+1&&tr[lc].cl>=0))
    {
//        printf("%d %d %d %d %d\n",tr[lc].cl,tr[lc].cr,tr[rc].cl,tr[rc].cr,md);
        tr[x].cl=tr[x].cr=-1;
    }
    else
    {
        if(tr[lc].cl!=-2)
        {
            tr[x].cl=tr[lc].cl;
        }
        else
        {
            tr[x].cl=tr[rc].cl;
        }
        if(tr[rc].cr!=-2)
        {
            tr[x].cr=tr[rc].cr;
        }
        else
        {
            tr[x].cr=tr[lc].cr;
        }
    }
}
void chg(int i,int l,int r,int x)
{
    if(l>r)
    return;
//    printf("%d %d %d\n",i,l,r);
    if(tr[i].l==l&&tr[i].r==r)
    {
        if(x)
        {
            tr[i].cl=l;
            tr[i].cr=r;
        }
        else
        {
            tr[i].cl=tr[i].cr=-2;
        }
        return;
    }
    pushdown(i);
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    chg(lc,l,r,x);
    else if(l>md)
    chg(rc,l,r,x);
    else
    {
        chg(lc,l,md,x);
        chg(rc,md+1,r,x);
    }
    pushup(i);
}
void chg2(int i,int l,int r)
{
    if(l>r)
    return;
    if(tr[i].l==l&&tr[i].r==r)
    {
        if(tr[i].cl==-2)
        {
            tr[i].cl=l;
            tr[i].cr=r;
            return;
        }
        else if(tr[i].cl==l&&tr[i].cr==r)
        {
            tr[i].cl=tr[i].cr=-2;
            return;
        }
    }
    pushdown(i);
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    chg2(lc,l,r);
    else if(l>md)
    chg2(rc,l,r);
    else
    {
        chg2(lc,l,md);
        chg2(rc,md+1,r);
    }
    pushup(i);

}
void get(int x)
{
//    print(x);
    if(tr[x].cl>=0)
    ans.push_back(make_pair(tr[x].cl,tr[x].cr));
    else if(tr[x].cl==-1)
    {
        get(tr[x].lc);
        get(tr[x].rc);
    }
}
int main()
{
    bt(0,131072);
    while(in())
    {
        l<<=1;
        r<<=1;
        if(!lt)
        l++;
        if(!rt)
        r--;
        if(type=='U')
        chg(1,l,r,1);
        else if(type=='I')
        {
            if(l>0)
            chg(1,0,l-1,0);
            if(r<131072)
            chg(1,r+1,131072,0);
        }
        else if(type=='D')
        chg(1,l,r,0);
        else if(type=='C')
        {
            chg(1,0,l-1,0);
            chg(1,r+1,131072,0);
            chg2(1,l,r);
        }
        else
        chg2(1,l,r);
    }
    memset(s,0,sizeof(s));
    get(1);
    for(int i=0;i<ans.size();i++)
    {
        while(i+1<ans.size()&&ans[i+1].first==ans[i].second+1)
        {
            ans[i].second=ans[i+1].second;
            ans.erase(ans.begin()+i+1);
        }
    }
    for(int i=0;i<ans.size();i++)
    {
        if(ans[i].first&1)
        printf("(");
        else
        printf("[");
        printf("%d,%d",ans[i].first/2,(ans[i].second+1)/2);
        if(ans[i].second&1)
        printf(")");
        else
        printf("]");
        printf(" ");
    }
    if(ans.size()==0)
    printf("empty set");
}