CF809D Hitchhiking in the Baltic States
Codeforces 分析 设 $f_{i, j}$ 表示前 $i$ 个数、LIS 长度为 $j$ 时末尾元素的最小值。 考虑转移。假设当前区间为 $[l, r]$，那么 不加：$f_{i, j} \gets f_{i - 1, j}$。 对于 $f_{i - 1, j -1} < l$，有 $f_{i, j} \gets l$。 对于 $l \leq f_{i - 1, j - 1...
Codeforces 分析 设 $f_{i, j}$ 表示前 $i$ 个数、LIS 长度为 $j$ 时末尾元素的最小值。 考虑转移。假设当前区间为 $[l, r]$，那么 不加：$f_{i, j} \gets f_{i - 1, j}$。 对于 $f_{i - 1, j -1} < l$，有 $f_{i, j} \gets l$。 对于 $l \leq f_{i - 1, j - 1...
Luogu 分析 首先应该可以一眼看出来这就是个 treap，然后改权值就相当于旋转。 考虑到 treap 旋转后中序遍历是不变的，因此我们可以先给所有节点按数据值排个序，这样就能得到中序遍历了。 进一步发现，中序遍历中一段区间在 treap 上是连通的一部分。因此可以考虑区间 DP。 设 $dp_{i,j,k}$ 表示 $[i,j]$ 内的节点，根节点权值 $\geq k$ 的最小代价。因...
GSS1 线段树上维护以下 $4$ 个东西： 区间和 区间最大前缀和 区间最大后缀和 区间最大子段和 合并两个区间应该比较简单，这里不再赘述。 GSS2 这题就很神仙了。 把所有询问离线并按右端点排序，然后从左往右扫。 对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。 设 $pre_i...
Luogu LOJ 分析 首先考虑怎么求出所有交点。 注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。 那么可以用 set 来维护 $y_{x,1}$ ，然后暴力求出所有交点。 因为交点个数 $\leq 500000$ ，所以可以过。 容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立的。 先考虑怎...