高维偏序问题

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

对于这类题目一般有三种通用方法,一是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的,还是求四维偏序的最长链。

 

偏序集

偏序关系

首先回顾一下偏序,集合X上的偏序是一个自反、反对称且传递的关系

  • 如果对于X中所有的x,都有x R x,则R是自反
  • 如果对于X中所有x和y,若x R y和y R x同时成立则x=y,则R是反对称
  • 对于X中所有的x,y和z,只要x R y且y R z,就有x R z,则R是传递

通常用\(\le\)取代R来表示偏序关系,常见的偏序关系有集合的包含,小于等于,整除等。\(<\)表示严格偏序(反自反,反对称,传递),比如严格包含于,小于关系等。

可比与不可比

对于X中x和y,如果x R y或者y R x,则说x和y是可比的,否则就说x和y不可比

极小元极大元

对于偏序集X中的元素a,不存在满足x<a的元素x,则a是偏序集的一个极小元。对于偏序集X中的元素b,不存在满足b<y的元素y,则b是偏序集的一个极大元。

链与反链

设\((X,\le)\)是有限偏序集,是X的一个子集C,它的每一对元素都可比,因此链C是X的一个全序子集,链的元素可以被线性排序。反链是X的一个子集A,他的任意两个元素都不可比。

由定义可知

链的子集也是链,反链的子集还是反链。

如果A是一个反链而C是一个链,则\(\left| A\cap C\right|\le 1\)

重要定理

定理1 设\((X,\le)\)是有限偏序集,设r是链的最大大小。则X可以被划分成r个反链,但不能划分成少于r个反链

定理2 (Dilworth定理) 设\((X,\le)\)是有限偏序集,设m是反链的最大大小。则X可以被划分成m个链,但不能划分成少于m个链

定理1的证明大概是每次找到偏序集的极小元集合,然后删掉,这样实际上得到的r个极小元集合就是划分成r个反链的方案。定理2是定理1的“对偶”定理,但是证明就比较复杂了。

题目

1.导弹拦截

最经典的题目,把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。这里的偏序关系i R j,可以理解为i<j且a[i]<a[j]。

2.2017 ICPC  Nanning The Maximum Unreachable Node Set

求一个DAG的最大的两两不可达的点集大小。

需要先做floyd,然后转化为求最小不相交路径覆盖就可以了,每个点拆成两个点,形成一个左右各n个点的二分图,对于一条边(i,j)左边的i连向右边的j,最终答案为n减去二分图最大匹配的数量。