关于加权的LIS问题

时间:2022-03-24 22:52:52

蒟蒻Zigzag正在准备联赛......

这个算是这几天做的唯一一个值得写一写的题吧。首先LIS的N^2暴力dp应该都会写,就是F[i]=Max{F[j]}+1

那么加权的就吧后面的1换成数的权值就行了,如果优先长度的话加一些判断就行了。

那么O(nlogn)怎么写?

LIS的Nlogn应该都会写,就是记一个数组D[i]表示长度为i的LIS的末尾的最小值,可证D是单增的,所以每次找Max的时候只需要二分查找D数组就行了

或者你可以个给每个F插到树状数组里(数为横坐标,F为纵坐标),每次查找比这个数小的里面的最大F

又或者可以用单调栈什么的?我记得好像可以,不过记不清了。

那带权的怎么写?

还想记录D数组吗?如果权值和很大的话开不起那么大的数组。树状数组也是一样,没那么大的空间。

其实这东西就是一个类似三维偏序的东西,如果把原始顺序看成x,数的大小看成y,权值和值看成z,于是每次就是找x和y都小于等于当前状态的一个最大的F值,你可以用平衡树来维护,但显然有点大材小用......

于是,想到了CDQ分治这个东西。

x维分治,y维快排,然后用一个单调栈来维护F。想想为什么不能直接单调栈?因为你只能一次把x维排序,那么我们把(y,F)看成平面上的点的话,那么每次加进来我们不能保证y是递增的,就无法维护。加上分治的好处就是我们可以保证加进来的点是单增的。

栗子请看RQNOJ的一个题