111qqz的小窝

老年咸鱼冲锋!

poj 2481 Cows(树状数组||线段树)

poj 2481 题目链接

题意:给定n个区间,问对于每个区间,有多少个区间真包含该区间(真包含的意思是说,两个区间不能完全重合)

思路:

下面是一年前用树状数组过掉的时候写的题解:
 和 star那道题差不多。

需要注意的是star那道题读入的时候已经排好了序,而这道题没有排序

由于答案是按照下表输出,排序的时候下标会被打乱,所以要存一下下表到结构体里。

另一个区别是,star那道题星星不会重复,就是说一个位置不会有多颗星星。

而这道题却可能,而且题目中说,如果区间的长度差为0(就是后面的那个不等式),那么不计数。

因为区间下标可能为0,但是树状数组的下表必须从1开始,所以下表要+1,但是由于下表可能有所重复,所以 不能用++,而是用+1

不然会增加多次(我就是这么w  a了两次。。。)

树状数组ac代码:

当然这道题也可以用线段树做。

先对点进行排序,右端点降序为第一关键字,左端点升序为第二关键字。(不唯一)

这样做有一个什么好处呢?

我们在处理第i个区间的时候,第i个区间前面的区间的右端点,一定是不小于第i个区间的右端点的,

此时我们只需要找到使左端点也满足题意的区间,也就是第i个区间前面的区间中,左端点不大于第i个区间的左端点的区间。

如果我们每次处理一个区间,都将该区间的左端点插入到线段树中(这句话可能比较抽象,线段树记录的是以某点为根节点的子树所代表的区间中点的个数,插入以后某一点记录为1,否则为0.),那么当我们询问第i个区间漆面的区间中左端点不大于第i个区间的左端点的区间的时候,其实也就是查询从1(这道题左端点的下标是从0开始,不过个人比较喜欢从1)到第i个区间的左端点之间有多少个点。

此外还需要注意两个区间重合的情况,这种情况是不能算在内的,要特殊处理。

 

线段树ac代码:

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363