UOJ Logo SHYI的博客

博客

[Sdoi2008]校门外的区间 题解

2016-07-30 15:57:06 By SHYI

题目大意:有5种运算维护集合S(S初始为空)并最终输出S。

  5种运算如下:

U T S∪T

I T S∩T

D T S-T

C T T-S

S T S⊕T

  基本集合运算如下:

A∪B
{x : xÎA or xÎB}

A∩B
{x : xÎA and xÎB}

A-B
{x : xÎA and xÏB}

A⊕B
(A-B)∪(B-A)

思路::每个数之间加入一个数,就像这样2 2.5 3 3.5 4 [2,3) -> [2,2.5] (3,4] -> [3.5,4] 用01表示集合,则U 区间涂1;I 两侧区间涂0;D 区间涂0;C 两侧涂0,中间取反;S 区间取反。用线段树解决,标记的下传很重要(被坑了)。

代码:

#include<cstdio>
#include<iostream>
#define n 131073
using namespace std;

int lazy[n<<2],num[n<<2],rev[n<<2];

int read()
{
     int x=0,y=0;
     char ch=getchar();
     while (ch<'0' || ch>'9')
     {
           if (ch=='(') y=1;
           ch=getchar();
     }
     while (ch>='0' && ch<='9')
     {
           x=x*10+ch-48;
           ch=getchar();
     }
     if (ch==')') y=-1;
     return x*2+y+2;
}

void push_down(int x,int l,int r)
{
     int y=lazy[x],z=rev[x];
     lazy[x]=-1,rev[x]=0;
     if (l==r)
     {
          if (y!=-1) num[x]=y;
          num[x]^=z;
          return;
     }
     if (y!=-1)
     {
         lazy[x<<1]=lazy[x<<1|1]=y;
         rev[x<<1]=rev[x<<1|1]=0;
     }
     rev[x<<1]^=z,rev[x<<1|1]^=z;
}

void add(int L,int R,int l,int r,int cur,int val)
{
     if (l>r) return;
     push_down(cur,L,R);
     if (l<=L && r>=R)
     {
           if (val<2) lazy[cur]=val;
           else rev[cur]^=1;
           return;
     }
     int mid=L+R>>1;
     if (l>mid) add(mid+1,R,l,r,cur<<1|1,val);
     else if (r<=mid) add(L,mid,l,r,cur<<1,val);
          else add(L,mid,l,mid,cur<<1,val),add(mid+1,R,mid+1,r,cur<<1|1,val);
}

int ask(int l,int r,int x,int cur)
{
    push_down(cur,l,r);
    if (l==r) return num[cur];
    int mid=l+r>>1;
    if (x<=mid) return ask(l,mid,x,cur<<1);
    else return ask(mid+1,r,x,cur<<1|1);
}

int main()
{
    char ch[9];
    for (int i=0;i<=n*4;i++) lazy[i]=-1;
    while (scanf("%s",ch)!=EOF)
    {
          int a=read(),b=read();
          if (ch[0]=='U') add(1,n,a,b,1,1);
          if (ch[0]=='I') add(1,n,1,a-1,1,0),add(1,n,b+1,n,1,0);
          if (ch[0]=='D') add(1,n,a,b,1,0);
          if (ch[0]=='C') add(1,n,1,a-1,1,0),add(1,n,a,b,1,2),add(1,n,b+1,n,1,0);
          if (ch[0]=='S') add(1,n,a,b,1,2);
    }
    int h=0,t=0,flag=0;
    for (int i=1;i<=n;i++)
        if (ask(1,n,i,1))
        {
            if (!h) h=i;
            t=i;
        }
        else
        {
            if (h)
            {
                if (flag) printf(" ");
                else flag=1;
                if (h&1) printf("(");
                else printf("[");
                printf("%d,%d",h/2-1,(t+1)/2-1);
                if (t&1) printf(")");
                else printf("]");
            }
            h=t=0;
        }
    if (!flag) printf("empty set");
    else printf(" ");
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。