注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3226][Sdoi2008]校门外的区间  

2015-01-12 20:06:55|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3226: [Sdoi2008]校门外的区间

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 359  Solved: 125
[Submit][Status]

Description

 
  受校门外的树这道经典问题的启发,A君根据基本的离散数学的知识,抽象出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)
 

Input

  输入共M行。
  每行的格式为X T,用一个空格隔开,X表示运算的种类,T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。
 

Output

 
  共一行,即集合S,每个区间后面带一个空格。若S为空则输出"empty set"。
 

Sample Input

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

Sample Output

(2,3)

HINT

对于 100% 的数据,0≤a≤b≤65535,1≤M≤70000

Source

线段树

Solution

首先把开闭区间统一转成闭区间,在 0.5、1.5、... 的位置加点,然后*2

在线段树上定义操作set,0为统一赋成0,1为统一赋成1,2为Xor(取反),-1表示什么事都没有发生。

五个操作解释成set如下:

U = set ( 1, l, r )

I = set ( 0, 0, l-1 ) & set ( 0, r+1, maxint )

D = set ( 0, l, r )

C = set ( 0, 0, l-1 ) & set ( 0, r+1, maxint ) & set ( 2, l, r )

S = set ( 2, l, r )

注意输入输出格式,小心TLE。

Code

/**************************************************************
    Problem: 3226
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:252 ms
    Memory:1096 kb
****************************************************************/
 
#include<cstdio>
char buf[1<<15],*S=buf,*T=buf;
inline char getc(){
    if(S==T)if(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)return 0;
    return*S++;
}
char t[1<<18],ch,op,lk,rk;
int d=1<<17,i,j,l,r,x,y,v,flag;
#define Xor(a) (a=1-a)
void update(int o,int l,int r){
    if(x<=l&&r<=y){
        v<2?t[o]=v:Xor(t[o]);
        return;
    }
    int mid=l+r>>1;
    t[o]==0||t[o]==1?t[o<<1]=t[o<<1|1]=t[o],t[o]=-1:
    t[o]==2?Xor(t[o<<1]),Xor(t[o<<1|1]),t[o]=-1:1;
    if(x<=mid)update(o<<1,l,mid);
    if(mid<y)update(o<<1|1,mid+1,r);
}
void set(int xx,int l,int r){
    if(l>r)return;
    x=l,y=r,v=xx,update(1,0,d-1);
}
void geta(){
    while(op=getc(),op!='U'&&op!='D'&&op!='S'&&op!='C'&&op!='I')
    if(op==0)return;
}
int main(){
    while(geta(),op!=0){
        getc(),lk=getc(),l=r=0;
        while(ch=getc(),ch!=',')l=l*10+ch-48;
        while(ch=getc(),ch>47&&ch<58)r=r*10+ch-48;
        rk=ch,l<<=1,r<<=1,l+=(lk=='('),r-=(rk==')');
        if(op=='U')set(1,l,r);
        if(op=='I')set(0,0,l-1),set(0,r+1,d-1);
        if(op=='D')set(0,l,r);
        if(op=='C')set(0,0,l-1),set(0,r+1,d-1),set(2,l,r);
        if(op=='S')set(2,l,r);
    }
    for(i=1;i<d;i++)
    t[i]==0||t[i]==1?t[i<<1]=t[i<<1|1]=t[i],t[i]=-1:
    t[i]==2?Xor(t[i<<1]),Xor(t[i<<1|1]),t[i]=-1:1;
    for(i=0;i<d;i++)if(t[i+d]==1){flag=1;
        for(j=i;t[j+d]==1&&j<d;j++);
        i&1?printf("(%d,",i>>1):printf("[%d,",i>>1),
        j&1?printf("%d] ",j>>1):printf("%d) ",j>>1),
        i=j-1;
    }
    if(!flag)puts("empty set");else puts("");
}
  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018