求助一种不用数据结构的CDQ分治写法
查看原帖
求助一种不用数据结构的CDQ分治写法
496840
SAMSHAWCRAFT楼主2022/8/7 23:16

按理说,CDQ 分治是可以互相嵌套的,同学和我各写了一个嵌套的 CDQ 分治,但是样例都过不了(陌上花开可过),简单翻了翻题解发现没有不用数据结构维护的 CDQ 分治做法。

我是这么写的,把删数改成加数,每个元素有三个属性 x,y,z 分别对应的是下标的相反数、数字、加入的时间。这样跑三维偏序再按时间给答案数组做一个前缀和应该就是要求的答案了。

比如说样例的元素就可以表示成:

(-5,2,2)
(-4,4,3)
(-3,3,1)
(-2,5,5)
(-1,1,4)

按照样例来说的话,数字 5 对数字 3 在时间为 1 的时候有一个贡献(3<2,3<5,1<5-3\lt-2,3\lt 5,1\lt 5),那么 f[1] 就应该不为 0 才对,但是我实际跑了一下发现 f[1] 是 0。

请问是 CDQ 分治哪里写的有问题还是说这个思路有错误的地方?恳请各位大佬指教,十分感谢!

2022/8/7 23:16
加载中...