社区讨论

求助一种不用数据结构的CDQ分治写法

P3157[CQOI2011] 动态逆序对参与者 3已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lo8cua4s
此快照首次捕获于
2023/10/27 16:31
2 年前
此快照最后确认于
2023/10/27 16:31
2 年前
查看原帖
按理说,CDQ 分治是可以互相嵌套的,同学和我各写了一个嵌套的 CDQ 分治,但是样例都过不了(陌上花开可过),简单翻了翻题解发现没有不用数据结构维护的 CDQ 分治做法。
我是这么写的,把删数改成加数,每个元素有三个属性 x,y,z 分别对应的是下标的相反数、数字、加入的时间。这样跑三维偏序再按时间给答案数组做一个前缀和应该就是要求的答案了。
比如说样例的元素就可以表示成:
CPP
(-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 分治哪里写的有问题还是说这个思路有错误的地方?恳请各位大佬指教,十分感谢!

回复

8 条回复,欢迎继续交流。

正在加载回复...