主题

主题

 
   

Segments

原题:http://acdream.info/problem?pid=1157

Problem Description

由3种类型操作:

1)D L R(1 <= L <= R <= 1000000000) 增加一条线段[L,R]

2)C i (1-base) 删除第i条增加的线段,保证每条插入线段最多插入一次,且这次删除操作一定合法

3) Q L R(1 <= L <= R <= 1000000000) 查询目前存在的线段中有多少条线段完全包含[L,R]这个线段,线段X被线段Y完全包含即LY <= LX<= RX <= RY)

给出N,接下来N行,每行是3种类型之一。

Input

多组数据,每组数据N

接下来N行,每行是三种操作之一(1 <= N  <= 10^5)

Output

对于每个Q操作,输出一行,答案。

Sample Input

6

D 1 100

D 3 8

D 4 10

Q 3 8

C 1

Q 3 8

Sample Output

2

1

Hint

注意,删除第i条增加的线段,不是说第i行,而是说第i次增加。

比如

D 1 10

Q 1 10

D 2 3

D 3 4

Q 5 6

D 5 6

C 2是删除D 2 3

C 4是删除D 5 6


个人解法:

其实如果告诉是CDQ分治还是挺好想的。(如果不告诉可能就要思考良久了……各种数据结构嵌套然后放弃……)

用CDQ分治了就很简单了。由于是计数问题,可以递归+归并,删去一个排序的log(虽然操作还是要一个log)。

把修改处理一下,插入与删除变为计数上的的+1与-1。

拿到左半部分与右半部分,均按照右端点排序(从大到小)。然后两个指针移动,保证左边修改的右端点全部大于或者等于当前询问的右端点,然后用一个树状数组维护修改的左端点。

查询,即查询当前修改的线段中左端点小于或者等于当前询问的左端点的线段有多少。

端点范围比较大,可能需要离散。


代码如下:

https://code.csdn.net/snippets/2279297


成功在ACdream排名Rank1。比较令人高兴的是,比某vjudge要跑得快……

 
 
评论