校门外的区间(interval)
【问题描述】
受校门外的树这道经典问题的启发，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)
【输入】
输入共m(m<=40000)行，每行表示一种操作第一个字符表示操作种类，之后一个空格，然后是一个区间
形如(i,j)或(i,j]或[i,j)或[i,j](0<=i<=j<=65535)
【输出】
输出最后集合S的所有区间，两个区间之间用空格分隔
线段树，我是将两个整数之间看为一个点，整数看为一个点，转换了一下区间
运用两个过程incr是把区间内所有数xor 1，fill是把区间内所有数赋成相同的值
U=fill(a,b,1)
I=fill(0,a-1,0)+fill(b+1,65535,0)
D=fill(a,b,0)
C=fill(0,a-1,0)+fill(b+1,65535,0)+incr(a,b)
S=incr(a,b)
之后查询所有点即可得到区间
program interval;
const
s=0;
e=131071;
var
m,i,j,k,a,b,tot:longint;
order,temp:char;
p,decr,left,right:array [0..3000001] of longint;
stop:array [0..3000001] of boolean;
procedure build;
begin
inc(tot);
left[tot]:=0;
right[tot]:=0;
p[tot]:=0;
stop[tot]:=true;
decr[tot]:=0;
end;
procedure down (now:longint);
begin
if left[now]=0 then
begin
build;
left[now]:=tot;
end;
p[left[now]]:=p[left[now]] xor decr[now];
decr[left[now]]:=decr[left[now]] xor decr[now];
if right[now]=0 then
begin
build;
right[now]:=tot;
end;
p[right[now]]:=p[right[now]] xor decr[now];
decr[right[now]]:=decr[right[now]] xor decr[now];
decr[now]:=0;
end;
procedure fill (a,b,point,l,r,now:longint);
var
mid:longint;
begin
if a>b then exit;
if (a=l)and(b=r) then
begin
stop[now]:=true;
decr[now]:=0;
p[now]:=point;
exit;
end;
mid:=(l+r) div 2;
down(now);
if stop[now] then
begin
decr[left[now]]:=0;
p[left[now]]:=p[now];
stop[left[now]]:=true;
decr[right[now]]:=0;
p[right[now]]:=p[now];
stop[right[now]]:=true;
stop[now]:=false;
end;
if b<=mid then fill(a,b,point,l,mid,left[now])
else
if a>=mid+1 then fill(a,b,point,mid+1,r,right[now])
else
begin
fill(a,mid,point,l,mid,left[now]);
fill(mid+1,b,point,mid+1,r,right[now]);
end;
end;
procedure incr (a,b,l,r,now:longint);
var
mid:longint;
begin
if a>b then exit;
if (a=l)and(b=r) then
begin
decr[now]:=decr[now] xor 1;
p[now]:=p[now] xor 1;
exit;
end;
mid:=(l+r) div 2;
down(now);
if stop[now] then
begin
decr[left[now]]:=0;
p[left[now]]:=p[now];
stop[left[now]]:=true;
decr[right[now]]:=0;
p[right[now]]:=p[now];
stop[right[now]]:=true;
stop[now]:=false;
end;
if b<=mid then incr(a,b,l,mid,left[now])
else
if a>=mid+1 then incr(a,b,mid+1,r,right[now])
else
begin
incr(a,mid,l,mid,left[now]);
incr(mid+1,b,mid+1,r,right[now]);
end;
end;
function find (who,l,r,now:longint):longint;
begin
if l=r then exit(p[now]);
down(now);
if stop[now] then
begin
decr[left[now]]:=0;
p[left[now]]:=p[now];
stop[left[now]]:=true;
decr[right[now]]:=0;
p[right[now]]:=p[now];
stop[right[now]]:=true;
stop[now]:=false;
end;
if who<=(l+r) div 2 then exit(find(who,l,(l+r) div 2,left[now]))
else exit(find(who,(l+r) div 2 + 1,r,right[now]));
end;
begin
assign(input,'interval.in');
reset(input);
assign(output,'interval.out');
rewrite(output);
tot:=-1;
build;
while not seekeof do
begin
read(order);
read(temp);
read(temp);
if temp='(' then k:=1
else k:=0;
a:=0;
repeat
read(temp);
if temp=',' then break;
a:=a*10+ord(temp)-48;
until false;
a:=a*2+k;
b:=0;
repeat
read(temp);
if (temp=')')or(temp=']') then break;
b:=b*10+ord(temp)-48;
until false;
if temp=')' then k:=-1
else k:=0;
b:=b*2+k;
readln;
case order of
'U':fill(a,b,1,s,e,0);
'I':begin
fill(s,a-1,0,s,e,0);
fill(b+1,e,0,s,e,0);
end;
'D':fill(a,b,0,s,e,0);
'C':begin
fill(s,a-1,0,s,e,0);
fill(b+1,e,0,s,e,0);
incr(a,b,s,e,0);
end;
'S':incr(a,b,s,e,0);
end;
end;
k:=-2;
for i:=0 to e do
begin
j:=find(i,s,e,0);
if j=1 then
begin
if i>k+1 then
begin
if i and 1 = 1 then write('(')
else write('[');
write(i div 2,',');
end;
k:=i;
end
else
if k=i-1 then
begin
write(i div 2);
if i and 1 = 1 then write('] ')
else write(') ');
end;
end;
if k=-2 then writeln('empty set');
close(input);
close(output);
end.