洛谷5568 [SDOI2008]校门外的区间

题意

挺简单的自己去看吧~

题解

因为有开闭两种区间，所以对每两个数中间也建一个点，总的点数即为 $2N$ 。

维护一个长度为 $2N$ 的 $0/1$ 序列，支持区间覆盖，区间翻转操作。令 $T=[l,r]$ （$l,r$ 为新编的点）：

1. U T：覆盖 $[l,r]$ 为 $1$
2. I T：覆盖 $[0,l-1],[r+1,2N]$ 为 $0$
3. D T：覆盖 $[l,r]$ 为 $0$
4. C T：翻转整个区间，再执行操作 $2$
5. S T：翻转 $[l,r]$

#include<bits/stdc++.h>

using namespace std;

const int N=65540*2;
struct Tree {
    int left,right,d;
    bool rev;
} tree[N<<2];
int s[N];

inline void pushdown(int x)
{
    if (tree[x].d!=-1)
    {
        tree[x<<1].d=tree[x<<1|1].d=tree[x].d;
        tree[x<<1].rev=tree[x<<1|1].rev=0;
        tree[x].d=-1;
    }
    if (tree[x].rev)
    {
        tree[x<<1].rev^=1;
        tree[x<<1|1].rev^=1;
        tree[x].rev=0;
    }
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    tree[x].d=-1;
    if (r-l>1)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
    }
}

void update(int x,int l,int r,int d)
{
    if (l<=tree[x].left && r>=tree[x].right) tree[x].d=d,tree[x].rev=0;
    else
    {
        pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x<<1,l,r,d);
        if (r>mid) update(x<<1|1,l,r,d);
    }
}

void reverse(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) tree[x].rev^=1;
    else
    {
        pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) reverse(x<<1,l,r);
        if (r>mid) reverse(x<<1|1,l,r);
    }
}

void query(int x)
{
    if (tree[x].left+1==tree[x].right)
    {
        if (tree[x].d==-1) s[tree[x].left]=0;
        else s[tree[x].left]=tree[x].d^tree[x].rev;
    }
    else
    {
        pushdown(x);
        query(x<<1);
        query(x<<1|1);
    }
}

signed main()
{
    build(1,0,N);
    char tg[5],ar[20];
    while (~scanf("%s %s",tg,ar))
    {
        bool lt=(ar[0]=='[');
        int l=0,i=1;
        for (;isdigit(ar[i]);i++) l=l*10+ar[i]-'0';
        int r=0;
        for (i++;isdigit(ar[i]);i++) r=r*10+ar[i]-'0';
        bool rt=(ar[i]==']');
        l<<=1; r<<=1;
        l+=!lt; r-=!rt; //[l,r]
        if (l>r) continue;
        if (tg[0]=='U') update(1,l,r+1,1);
        else if (tg[0]=='I') update(1,0,l,0),update(1,r+1,N,0);
        else if (tg[0]=='D') update(1,l,r+1,0);
        else if (tg[0]=='C') reverse(1,0,N),update(1,0,l,0),update(1,r+1,N,0);
        else reverse(1,l,r+1);
    }
    query(1);
    bool flag=0;
    for (int i=0;i<=N;i++)
    {
        if (!s[i]) continue;
        flag=1;
        int j=i;
        for (;s[j+1];j++);
        if (i&1) printf("(%d,",i>>1);
        else printf("[%d,",i>>1);
        if (j&1) printf("%d) ",(j+1)>>1);
        else printf("%d] ",j>>1);
        i=j;
    }
    if (!flag) puts("empty set");
    return 0;
}