线段树做法

liu_cheng_ao 2018-04-04 11:30:54 2018-04-04 11:31:40

用一个线段树维护每个节点每种前缀 or 和以及每种后缀 or 和,然后暴力算出这两者一一对应的最优 or 和 …… 再用一组堆维护每种长度上述所有的 or 和,再用一棵二叉查找树(我用了线段树)维护每种长度 or 和的最小代价。查询时二分即可。

时间复杂度 O(q\log^2n\log^2a) ,其中修改一次的复杂度为 O(\log^2n\log^2a) ,查询一次的复杂度为 O(\log n)

这个复杂度非常不平衡 …… 不知能否优化。

四个 \log 本来是过不去的,加了一些奇怪的常数优化。

代码

共 2 条回复

kczno1

因为我造数据时知道的方法都是修改比询问快的。。
所以修改的比例比较低。。

kczno1

您跑的最慢的,接近1.5s的点竟然是10000,10000的