首页 > 题解 > bzoj 3226 [Sdoi2008]校门外的区间

bzoj 3226 [Sdoi2008]校门外的区间

Description

  受校门外的树这道经典问题的启发,A君根据基本的离散数学的知识,抽象出5种运算维护集合S(S初始为空)并最终输出S。现在,请你完成这道校门外的树之难度增强版——校门外的区间。

Markdown

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

题解

这是非常明显的线段树。

把每一个区间里插上一个数表示开区间的情况。

U 区间涂1
I 两侧区间涂0
D 区间涂0
C 两侧涂0,中间取反
S 区间取反

但是昨天写线段树要写吐了。那就写写分块吧。

好像跑得飞快?

Markdown

扔个生产器


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×