DS

CF1672H

已收录

CF1290E

大根笛卡尔树子树大小就是当前点作为最大值的区间, 于是想到逐个插入维护左右端点, 但相邻两个插入的元素之间未被插入元素多算的贡献是不好去除的, 所以需要插入的时候不是插入的原序列对应位置上而是无空隙紧挨着插入, 每次是区间取max/min和区间加.

CF809D

LIS两个主要做法分别是记录以某值结尾的最短长度和某长度对应的最小结尾. 此题一维表示当前前 $i$ 个数, 若第二维表示当前的值那么转移是跳跃的, 如果记录长度则是连续的.

于是 $f_{i, j}$ 表示前 $i$ 个, 长度为 $j$ 的结尾最小值, 那么显然

$$
f_{i, j}=\max f_{i-1, j},
\begin{cases}
f_{i-1, j-1}+1, f_{i-1, j-1}+1\in [l_i, r_i]\
l_i, f_{i-1, j-1}+1<l_i\
inf, f_{i-1, j-1}+1>r_i
\end{cases}
$$

显然 $f_i$ 是递增的, 考虑数据结构维护状态, 那么第二种转移显然就是直接区间赋值了, 而第一种转移需要平移之后和原来的比较, 发现不用比较: $f_{i-1, j}$ 一定是某一 $k$ 由 $f_{k, j-1}$ 转移到了 $k$, 此时发现 $f_{i-1, j-1}\le f_{k, j-1}$, 所以可以不需要考虑max, 于是就成了平移, 平衡树好做的.

CF1648D

考虑dp, 走到 $(2, i)$ 的代价为 $f_i$

那么要走到这个位置至少要点亮一个区间, 有两种情况, 在这个区间的范围内从第一行进入当前行走过来, 或者从区间左端点上一个过来.

那么考虑如何转移, 这个区间要包含当前点, 排序后是一个区间, 第一种情况的值可以直接挂钩到区间上, 第二种看来也可以, 于是直接线段树维护.

CF407E

等差数列先要同余, 于是先处理出同余段, 相同元素可以按照不同余处理划成两段, 然后只需关心 $b_i=\lfloor \dfrac{a_i}{d}\rfloor$, 要求是一个连续的值域段. 也就是 $max-min+k\ge r-l$. 那么扫一个右端点, 维护 $max-min+l$, 单调栈配线段树

CF1423G

考虑一个位置 $p$ 的贡献, 若它上次出现位置为 $lp$, 那么考虑这个区间出现的左端点, 贡献就是 $\min(i, n-k+1)-\max(lp+1, i-k+1)+1$, 然后发现可以把 $\min, \max$ 拆开, 因为这个等价于四种中最小的, 于是变成了

$$
f_i(k)=\min{i-lp, k, n-i+1, n-k-lp+1}
$$

这个是关于 $k$ 的分段一次函数, 最多有三段(有两个是常函数), 那么直接维护出分界点, 查询就是对落在第一段, 第二段, 第三段的分别求个和.

而修改是简单的, 因为只有 $lp$ 会被改, 所以同镜中的昆虫, 颜色段均摊即可.

复杂度是单log.

IOI13 Wombats

给定一个 $n\times m$ 的网格图, 边有边权, 不允许向上走. 有 $q$ 次询问:

  • 修改网格图上一条边的边权.
  • 询问从第一行某点走到最后一行某点的最短路径长度.

$n\le 5000, m\le 200, q\le 2\times 10^5$, 最多 $500$ 次修改.

考虑在行上建线段树, $f_{u, i, j}$ 表示从 $(l, i)$ 走到 $(r, j)$ 的最短距离, 其中 $(l, r)$ 表示 $u$ 代表的区间, 这是 $(\min, +)$ 卷积, 此时合并一次是 $m^3$, 总复杂度是 $m^3(500\log 5000+n)$

考虑合并 $g_{i, k}$ 和 $h_{k, j}$ 得到 $f_{i, j}$ 的过程中, 随 $j$ 增加, $k$ 一定也是增的, 证明可以考虑路径不会相交(可以有公共点, 但不会交完走向两边), 决策单调性, 那么二分分决策点成了 $m^2\log$.

考虑刚才的证明可以发现 $p_{i, j}\in (p_{i-1, j}, p_{i, j+1})$, 复杂度 $m^2$.

LOJ6507

拆位再线段树无论如何都有两个log.

考虑and和or都是丢信息的, 于是对线段树的每个节点以不全相同的位的个数为势能, 这样and和or都是单减的, 于是对当前节点, 没有影响就不更新, 如果有影响直接递归, 因为有影响一定会让势能减少, 总势能一开始 $n\log A$, 于是复杂度 $n\log A$

UOJ191

只删不增你一定会动态构建线段树, 线段树节点上建凸包.

直接加删除会被卡, 因为删一个再加一个就可以付出 $O(len)$ 的代价.

解决方案是, 只有当自己同层的右边一个点可以建点了, 才合并成线段树上一个点, 于是删除的代价也均摊掉了. 好厉害!

CF1340F

楼房重建线段树经典题

BZOJ2138

picture 0

String

UVA11022 String Factoring

区间dp, $f_{l, r}$ 表示的答案, 转移要么是拼接, 要么是求循环节, 用 KMP 求 border 即可. $n^3$

CF696 Legen. . .

我还以为这题目名字没打全

基本上, 你想要一个DFA, 包含所有整串, 所以直接建出AC自动机, dp就记录当前长度和走到了DFA的哪个节点上, 然后因为 $l$ 的范围优化成矩阵快速幂.

P3311 [SDOI2014]数数

数位dp, 状态记录走到自动机哪个位置即可.

P2414 [NOI2011]阿狸的打字机

打字过程可以看成在字典树上走(前缀是公共的).

然后发现AC自动机中, 求x在y中的出现次数相当于走一遍 $y$, 看有多少次 $y$ 的fail出现在 $x$ 的子树中, 而每次走一遍 $y$ 爆炸了, 于是离线dfs一遍即可. 问题变成单点加子树求和.

CF587F Duff is Mad

仍然AC自动机, 走一遍 $s_k$, $fail$ 出现在 $s_l\ldots s_r$ 中的和, 此时想到两种暴力, 对 $s_k$ 的每个前缀求自己被多少个 $s_l\ldots s_r$ 的元素包含, 对每个 $s_l\ldots s_r$ 求包含多少个 $s_k$ 的前缀. 于是根号分治, 如果 $s_k>B$, 则 $s_l\ldots s_r$ 中可能包含 $s_k$ 的只有 $\dfrac{n}{B}$ 个, 直接用第二种暴力, 复杂度 $s\dfrac{n^2}{B}$; 如果 $s_k<B$, 则遍历 $s_k$ 的代价成了 $B$, 对每个前缀求编号区间中包含一个点的区间个数, 是二维偏序, 那先差分编号, 扫编号, 然后dfs序变成区间加单点查, 复杂度 $nB\log n$, 平衡成 $n\sqrt{n\log n}$

String

异或最小生成树

经典的, brovka+全局trie+每个联通块一个trie

几个怪题

他都不把范围说清楚啊

一个图, 询问集合 $S$ 和集合 $T$ 之间的最短路.

建源汇

一个图, 询问集合 $S$ 里面的点, 两两点距离最小值

边权是正的的话, 多源bfs直到两个源扩展出的相交

平面上给出 $n$ 个点, 求一个一般图最大权匹配. 两点间边权为 $\max{\vert x_i-x_j\vert, \vert y_i-y_j\vert}$

可以把绝对值拆了, 四个中取最大.

于是建四个点表示取四种最大, 每个点向四个点连边可以把图建出来了.

好吧现在虽然没有会这个题, 但直接网络流就会了AGC034D(二分图版+模拟费用流)

P3825 [NOI2017] 游戏

考虑 $d=0$ 时每个地图只有两种选择是2sat, 那么直接暴力枚举剩下 $x$ 是哪种地图, 只用枚举两种, 复杂度 $2^dn$.