高维偏序问题

最近做了几道高维偏序的简单题。

对于这类题目一般有三种通用方法,一是cdq分治,维数越多嵌套次数就越多,总体来说思路就是对时间分治,每次统计出左半区间的贡献点对右半区间的询问点的贡献,这样对于每个询问点来说,它前面的所有对它造成影响的点就都会被算到。二是用bitset优化暴力,应该只能处理计数问题,但优点是好写,适合做高维偏序。三是KDtree,emmmm,这个没怎么写过,多校训练十分艰难的写过一次,通过了90%的数据然后TLE了。

1.LOJ#112 三维偏序

计数题,对其中一维排序后,cdq分治套树状数组,时间复杂度\(O(nlog^{2}n)\)

2.COGS 2479 [HZOI 2016] 偏序

计数题,四维偏序,cdq分治套cdq分治套树状数组,时间复杂度\(O(nlog^{3}n)\)。

怎么理解这个分治套分治呢。假设属性为a,b,c,第一次分治的时候我们将区间[l,mid]的点标记成贡献点,[mid+1,r]的点标记成询问点,然后区间[l,r]按a属性排序,消去a的影响,这样问题就变成了有n次操作,每次要么插入一个点(b,c),要么查询之前插入的点中有多少点在(b,c)左下方,这样问题就降了一维化成了三维偏序了。 

3.COGS 2580 [HZOI 2015]偏序 II

计数题,五维偏序,在上一题的基础上外面再套一次cdq分治,时间复杂度十分感人\(O(nlog^{4}n)\)。

 

4.COGS 2639. [HZOI 2015] 偏序++

计数题,七维偏序。只能bitset了,每个元素开一个bitset表示哪些点比它小,一维一维的考虑,从小到大枚举值,然后对每个元素and一下就行了。时间复杂度\(O(kn^2/64)\)

 

5.SPOJ LIS2 Another Longest Increasing Subsequence Problem

求最优解,即最长上升子序列的长度,每个元素有两个属性。回忆一下一个属性的话,我们可以用树状数组求前缀最大值的方法优化dp的转移,再加一维就用cdq分治套一下就行了。

与之前计数题不同的地方在于,计数题中贡献对询问的影响是独立的,没有先后顺序的问题,但是做这个dp的过程就必须是从前往后了,比如说序列1,2,3,4,如果用3去更新4的话,3的dp值就必须在之前就已经算出来是3。稍微改一下分治的顺序就可以了,先递归到[l,mid],然后用左半区间更新右半区间的dp值,然后递归到右半区间。

6.2018 牛客网暑期ACM多校训练营(第九场)Longest Common Subsequence

求四个序列的最长公共子序列,保证值范围1-n,前三个序列中每一种值出现次数不超过2次。

先考虑四个序列都是排列的情况,假设对于值x来说pa[x],pb[x],pc[x],pd[x]在四个序列中的位置,那么最长公共子序列就转化成了求四维偏序的最长链。对于这个题目我们可以2的3次方枚举每个值的位置三元组,这样总点数就是8n的,还是求四维偏序的最长链。