codeforces 19 D. Points (离散化+树套树(线段树+set))

题目链接

题意:

在二维坐标平面内进行n (1 ≤ n ≤ 2·105) 次操作。一共有三种类型操作。

1.add x,y 将点(x,y)加进坐标系。

2.remove x,y 将点(x,y)移除.

3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。

x,y均为非负数。以上操作均合法。

思路:没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。

大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz

很巧妙得把二维问题转化成了一维问题。。。

我来说一下大概做法,具体的细节见代码注释:

在x轴方向维护一课线段树,线段树的数组tree[i]存储的信息是以i节点为根节点的子树所对应的区间能达到的最大的y值。线段树的叶子节点上是一个set,set[i]是横坐标为i时的纵坐标集合,也就是所谓的树套树。

由于x很大,但是n比较小,所以我们这里采用了stl+去重的办法离散化离散化的三种办法

对于添加和删除点的操作,我们更新完对应的set把相应的x(离散化后的)在线段树中更新就好(因为线段树的update操作是和set有关的)

对于find操作,我们首先从线段树中找到(下标大于x且最小且集合中存在大于y的元素的集合)的下标

这样我们确定了x,再upper_bound一下找到对应的集合中最小的y.

初始化由于没有插入y,所以tree可以初始化为-1,不用建树。。。(反正建了也都是-1)

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz