bzoj 3226 [Sdoi2008]校门外的区间(线段树)

3226: [Sdoi2008]校门外的区间

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 615  Solved: 227
[Submit][Status][Discuss]

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

【思路】

线段树。

因为开区间所以扩大一倍就好了。

   转化集合操作为线段树上的操作

U 将a,b设为1

I 将1..a-1,b+1..n设为0

D 将a..b设为0

C 将1..a-1,b+1..n设为0 取反a..b

S 取反a..b

写一个支持set与取反的线段树。

【代码】

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std; const int N = +; struct Tree{ int l,r,v,setv,rev; }T[N<<]; void build(int u,int L,int R) {
T[u].l=L,T[u].r=R,T[u].setv=-;T[u].rev=;
if(L==R) return ;
int M=(L+R)>>;
build(u<<,L,M); build(u<<|,M+,R);
}
void pushdown(int u) {
int lc=u<<,rc=lc|;
if(T[u].l==T[u].r) {
if(T[u].setv!=-) T[u].v=T[u].setv;
T[u].v^=T[u].rev;
}
else {
if(T[u].setv!=-) { //AT: set->rev=0 所以rev的执行顺序在set之后
T[lc].setv=T[rc].setv=T[u].setv;
T[lc].rev=T[rc].rev=;
}
T[lc].rev^=T[u].rev,T[rc].rev^=T[u].rev;
}
T[u].setv=-, T[u].rev=;
}
void update(int u,int L,int R,int x) {
pushdown(u);
if(L<=T[u].l && T[u].r<=R) {
if(x==-) T[u].rev^=;
else T[u].setv=x;
}
else {
int M=(T[u].l+T[u].r)>>;
if(L<=M) update(u<<,L,R,x);
if(M<R) update(u<<|,L,R,x);
}
}
int query(int u,int x) {
pushdown(u);
if(T[u].l==T[u].r) return T[u].v;
else {
int M=(T[u].l+T[u].r)>>;
if(x<=M) return query(u<<,x);
else return query(u<<|,x);
}
}
void reverse(int u,int L,int R) { update(u,L,R,-); } char s[];
void read(int& x) {
char c=getchar(); int f=; x=;
while(!isdigit(c)) { if(c=='(') f=; c=getchar(); }
while(isdigit(c))
x=x*+c-'' , c=getchar();
if(c==')') f=-;
x=x*+f;
}
int main() {
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
int n=*+;
build(,,n);
while(scanf("%s",s)==) {
int a,b;
read(a),read(b);
a+=; b+=;
switch(s[]) {
case 'U':
update(,a,b,); break;
case 'I':
update(,,a-,),update(,b+,n,); break;
case 'D':
update(,a,b,); break;
case 'C':
update(,,a-,),update(,b+,n,);
reverse(,a,b); break;
case 'S':
reverse(,a,b); break;
}
}
int f=-,r=-,flag=;
for(int i=;i<=n;i++)
{
if(query(,i)) { if(f==-) f=i; r=i; }
else {
if(f!=-) {
if(flag) putchar(' ');
else flag=;
if(f&) putchar('(');
else putchar('[');
printf("%d,%d",f/-,(r+)/-);
if(r&) putchar(')');
else putchar(']');
}
f=r=-;
}
}
if(!flag) puts("empty set");
return ;
}
上一篇:数据文件resize扩容


下一篇:Codeforces Round #404 (Div. 2) A,B,C,D,E 暴力,暴力,二分,范德蒙恒等式,树状数组+分块