一行超人

题目链接  或  题目链接  

题目大意：求n个4维空间的点x[n]的最长不降序列。$n<=50000$保证坐标在$[0,m)$随机生成

测试点1

$n<=2000$

容易想到利用$dp$来解决问题。

我们可以先排序，第一关键字为第一维坐标，第二关键字为第二维坐标……，这样排序之后我们发现一个点i只能成为排序之后排在它前面的点的后继。那么令$dp[i]$表示以i结尾的最长不降序列。

那么有状态转移方程：$$dp[i]=max(dp[j]+1) j<i且x[i]>=x[j]$$

其中$x[i]>=x[j]$表示i点的所有坐标都>=j点的坐标

时间复杂度$O（n^2）$。可以通过第一个测试点。

测试点2  

$n<=50000$，所以$O（n^2）$的算法行不通。

但是注意到$m<=8$。所以本质不同的点（也就是把四维坐标全部一样的缩成一个点）最多只有$8^4=4096$个。

所以我们直接构造出$8^4$个点，然后$w[i]$表示$i$这个点出现了多少次。那么按照一维排序后。

新的$dp$方程：$$dp[i]=max(dp[j]+w[i]) j<i且x[i]>=x[j])$$

复杂度$O(8^8)=O(1)$ 

测试点3-4

$n<=50000$但是有两维坐标全部相同 

所以这就是一个二维的最长不降序列问题。还按照上面的方法排序。

$dp$方程还是上面的形式，而$dp[i]$只会被$j<i且x[j][2]<=x[i][2]$的$dp[j]$来更新。

所以我们可以以$x[i][2]$为下标建立一个数组$b[y]$表示$x[i][2]==y$中的$dp[i]$的最大值。

然后按$i=1到n$的顺序$dp$。

我们需要一个数据结构支持 前缀最大值查询以及单点修改。

可以用线段树实现。也可以用树状数组来实现。

时间复杂度$O(nlogn)$ 

测试点5-6   

$n<=50000$但是有一维坐标全部相同

这是一个三维的问题。

每个$dp[i]$会被$j<i且x[j][2]<=x[i][2]且x[j][3]<=x[i][3]的dp[j]$更新。

我们沿用上面的思路。有两维限制的话我们可以考虑用树套树解决。

树套树可以有很多做法。比如线段树套线段树，树状数组套$treap$等等。

具体的话，比方说我们用树状数组套$treap$来做。

那么每一个树状数组的节点维护了一棵属于该节点管辖范围的以$x[j][3]$为权值的treap。

查询的时候沿着树状数组往前跳，每次在treap里面查找$<=x[i][3]$的最大$dp$值即可。

线段树套线段树+动态开点也可以达到同样的效果。

时间复杂度$O（nlog^2n）$

空间复杂度$O（nlog^2n）$

测试点7-8  

$n<=50000  m<=100$

树套树套树？

注意到m很小，所以我们可以直接建立一个三维的树状数组！

空间复杂度$O（m^3）$

时间复杂度$O（nlog^3 100）$

测试点9-10  

$n<=50000$

如果我们用线段树套线段树套线段树的话，空间复杂度是$O（nlog^3n）$的。

会因为常数较大而导致TLE和MLE。

我们考虑一种新的思路：$K-D tree$。

我们把$x[i][2] x[i][3] x[i][4]$作为3个坐标放到3维空间中，这样我们每次都是对三维空间中的一个区域查询点的最值，

或者修改一个点的权值。

这个可以很简单的用$K-D tree$来实现。

关于K-D tree的高维空间区域查询的方法可以看我另一篇文章

复杂度$O（n^{1-1/3})=O(n^{\frac{2}{3}})$

代码

其他算法  

 

二维偏序最长链我们可以很方便的用树状数组来解决。

三维偏序最长链问题我们可以考虑利用CDQ分治。

定义过程$solve（l，r）$表示求解$[l,r]$的答案。

那么CDQ分治的算法过程为

$solve(l，mid)$

处理$(l,mid)$对$(mid+1,r)$的影响。

$solve(mid+1,r)$

考虑用这个来解决三维偏序最长链问题，那么只需要考虑处理$(l,mid)$对$(mid+1,r)$的影响。

我们发现这时候我们就消除了第一维对我们解决问题的影响。我们就可以按第二维坐标排序，然后该修改修改，该查询查询。

所以这个问题就转化成了二维的问题。

四维的可以一层CDQ分治变成三维的问题，继续CDQ分治变成二维的问题。

具体实现可以看代码 

时间复杂度$O(nlog^3n)$

因为CH评测机很快常数较小所以可以通过所有测试数据。

一些其他的东西  

Q:为什么数据是随机的呢？

A:其实一开始让我数据随机，其实我是是拒绝的。

  因为数据一随机，一些奇怪的乱搞可能就艹标程了。

  但后来**跟我讲，数据不随机，K-D tree可能被卡，标程被cha就不好办了。

  于是duang的一下。这题数据就变成随机了。

于是松爷就乱搞艹过了

Q:某神犇：这题为什么这么多部分分？我分分钟AC都拉开不了分差

A：其实因为iwtwiioi和laekov出的题太毒瘤了，所以这道题就出成良心送分题了，大家得分都很高也很happy啊。

另外iwtwiioi还有一种树套树套树的简单写法。尽管由于空间问题并不能通过此题，但是这个写法是十分值得借鉴的。

代码

最后

我比较弱所以如果哪里说得不清楚或者哪里有问题或者哪里叙述的不正确欢迎与我讨论。

感谢大家参与此次互测。