[BZOJ3262/Luogu3810]陌上花开(CDQ分治,树状数组)

发布于 2018-03-26  7 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3262/Luogu3810]陌上花开(CDQ分治,树状数组)

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Tag

CDQ分治,树状数组

题目大意

求三维偏序。

解决思路

学习三维偏序。对于三维偏序(a,b,c),首先在外面把第一维排序,这样,下面的过程就不需要考虑第一维的影响了。
然后我们二分区间,每一次只考虑左边对右边的贡献,那么因为在外面的时候a已经是有序的了,所以可以保证左边的a一定小于等于右边的a,所以相当于是按照第二维b来进行类似归并排序的操作,对于右边的bi,统计比它小的左边的bj对应的cj有多少不大于ci,那么这个值域的问题可以用树状数组来维护。
需要注意的是,由于有可能有重复的花,所以要先去重。另外,每一次清空树状数组会浪费大量的时间,所以可以用一个时间戳来标记。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3262/Luogu3810]陌上花开(CDQ分治,树状数组)


HNCJ OIer 一枚