LaIS *2200

没太想出来。

设 $f_i$ 表示以 $i$ 为结尾的最长子序列长度。

考虑如何从 $j$ 转移到 $i$。

若 $a_j\le a_i$，那么直接转移即可。

若 $a_j > a_i$，则需要考虑 $j$ 的前驱 $k$。

因为需要满足 $\min(a_k,a_j)\le \min(a_j,a_i)$，即 $a_k \le a_i$。

那么我们贪心的想，让 $j$ 越靠右越好，因为这样前驱 $k$ 的范围就更大。

那么我们维护一个单调栈，求出每个 $i$ 左侧的第一个 $j$，使得 $a_j > a_i$。

转移用树状数组即可。

复杂度 $O(n\log n)$

Helping Hiasat *2200

开到抽象题了。

第一遍读错题了，没看到每一次都得一样。

如果没有这个限制的话就很简单了，把相邻两个 $1$ 之间划分成一个区间，找每个区间的众数即可。

但现在有这个限制，怎么办？

依旧考虑划分成若干区间，那么两个人可以共存当且仅当两个人从未同时出现过。

如果两个人不能共存，那么就连一条边。最后求出这个图的最大独立集即可。

这是一个 $NPC$ 问题。

不过有结论：原图的最大独立集=补图的最大团。

最大团可以用 Bron–Kerbosch 算法在 $O(2^{\frac{n}{2}})$ 的复杂度内求出。

复杂度 $O(nm^2+2^{\frac{m}{2}})$

Demiurges Play Again *2200

首先考虑权值给定怎么做。

设 $f_{u,0/1}$ 表示 $u$ 点先/后手能取到的值。转移为

$$f_{u,0}=\max_{v \in sub_u} f_{v,1} \\ f_{u,1}=\min_{v \in sub_u} f_{v,0}$$

然后考虑放权值。

依旧设 $f_{u,0/1}$，表示 $u$ 点先/后手能取到的值是该子树内第 $f_{u,0/1}$ 大的数。

那么转移是类似的，不过变成了第几大。

对于 $f_{u,0}$，取 $\min$ 即可。

对于 $f_{u,1}$，下一步由对方取最大值，而无论怎么放权值，对方都有可能不选择某子树。所以问题可以看作我们需要放多少个数进入叶子结点才可以让此时的玩家保证能够取到数。而能取到的最小值就是这些数的最后一个。因为是子树内的第几大，所以可以直接求和。

综上，转移为

$$f_{u,0}=\min_{v \in sub_u} f_{v,1} \\ f_{u,1}=\sum_{v \in sub_u} f_{v,0}$$

那么答案分别为 $m-f_{1,0}+1,f_{1,1}$。

复杂度 $O(n)$

因为有单调性，所以也可以二分变成判定性问题，不过似乎有点多此一举？

Yet Another Array Counting Problem *2300

开到了笛卡尔树上 dp 板子。

以下标为键，$a_i$ 为值建立大根笛卡尔树，那么 $[l,r]$ 的最左端最大值位置就是 $l,r$ 在笛卡尔树上的 $\operatorname{lca}$。

那么所有最左端最大值位置都相等，就意味着笛卡尔树的形态相同。

此时转化为树计数问题。

设 $f_{u,i}$ 表示 $u$ 取值 $1 \sim i$ 的方案数。

左儿子可以填 $[1,i-1]$，右儿子可以填 $[1,i]$

转移就是 $f_{u,i}=f_{u,i-1}+f_{ls_u,i-1}\times f_{rs_u,i}$

复杂度 $O(nm)$