T3好像写过，想了一会会了，写的挺顺的，顺带卡了卡常数。
T1给我的直觉是最小割，但是想了一会不知道怎么建图。
后来想了想写了个状压dp，插头dp可以拿到55，但是似乎比较麻烦。
随机数列的lis的期望是
n
\sqrt n
n，但是这个题要求构造的
2
n
2\sqrt n
2n
写了一下发现的确有的时候会被卡。
自闭。
T2想了个神奇的构造，找出n组，从整体来看，每组单调上升，但是每组内部可以降序。
似乎随机的话都能构出来。希望出题人不回卡这种做法。
因为要输出方案，实现起来很复杂，一开始写的时候还要树套树，后来优化到了
O
(
n
2
)
O(n^2)
O(n2)
大概可以有70pts
写插头dp，但是没有调出来。
考场降智。第一直接是最小割是对的，不过一直想不到怎么建图。
看来还是二分图和最小割建图不太熟，不过55的插头dp没写出来不应该。
要刷一点最小割的题。
神仙的构造。
把原序列分成
n
n
n块，每次选一个次大值最大的块，把这个块的最大值和次大值选中，然后把这个块删除。然后把其他块的最大值删除。
可通过归纳证明这样构造符合题意。
然后用个堆维护就可以做到
n
l
o
g
n
nlogn
nlogn