搜索
CatchThePenguins杭州学军中学张闻涛问题简述•给出四维空间上N个企鹅坐标。•有Q个询问，每次给出一个点，问有多少企鹅每一维坐标都小于等于这个点。样例输入•１•0000•2•1111•111-1样例输出•１•０数据范围数据编号NＱ1~2N=５000Ｑ＜＝５０００3~6N=1０000Ｑ＜＝１００００7～１４Ｎ＜＝３００００Ｑ＜＝１００００１５～１８Ｎ＜＝１００００Ｑ＜＝３００００１９～２０Ｎ＜＝３００００Ｑ＜＝３００００算法０•暴力枚举询问•暴力枚举企鹅•判断•时间复杂度O(n^2)•期望得分10分。算法０优化•企鹅按四维坐标排序•得到四个排序数组•对于每个询问，每一维在这四个数组里二分•得出这一维小于询问坐标的企鹅的个数•取其中最小的进行枚举（常数优化）•期望得分3０分。2/28/2020继续优化？•在线算法难以再继续下去•离线处理分块算法离散化。•离线。•分别将询问和企鹅按照第一维坐标排序•按第一维坐标从小到大枚举询问。对于每个询问：•加入所有第一维比它小的企鹅。•按照第二维排序•每加入sqrt(n)个企鹅，就暴力进行一次排序•其余：暴力。•这部分总复杂度Ｏ(nsqrt(n))。当进行一次暴力排序时：•已经加入排序的企鹅的个数为M•分成大小为sqrt(M)的块•按照第三维坐标排序•按第四维维护前缀的权值线段树•函数式线段树询问：•整块：二分+查询•非整块：暴力•总复杂度O(nsqrt(n)log(n))•期望得分80分更优算法•离散化。•离线更优算法•将询问和企鹅一起按第一维坐标排序。•分治：•按照第二维坐标进行“归并”。更优算法•设排好序后的编号序列为id[L]~id[R]，令MID为其中点。•先递归处理L~MID，MID+1~R部分的答案•归并，每次选取左右两部分中的较小值：–左边的企鹅：将其加入一个集合–右边的询问：询问集合中第三、四维坐标比它小的企鹅数2/28/20202,33,32,33,33,14,43,14,43,52,34,54,22,65,53,31,43,52,34,54,22,65,53,31,4经过分治，第二维坐标有序由于初始按第一维排序，所以左侧第一维坐标=右侧开始按第二维“归并”6,63,76,63,72/28/20202,33,32,33,33,14,43,14,43,52,32,65,53,52,34,54,22,65,53,31,4开始按第二维“归并”6,63,76,63,73,35,54,4ans+=1ans+=33,14,44,54,2ans+=12,33,33,31,43,52,32,65,56,63,7ans+=3•实现：•树状数组/线段树套平衡树。•总时间复杂度O(nlog^3(n))•期望得分100分。回顾原问题无实质性优化在线暴力算法一眼看出寻求优化分块算法尝试离线寻找更优算法分治树套树解决问题2/28/2020考察点•从在线到离线的思维转换•分块、分治等思想的运用•数据顺序的巧妙处理•数据结构的熟练掌握2/28/2020预计得分情况0510152025303540450102030405060708090100分数人数人数谢谢观看欢迎提问