Solutions
Link Cut Tree (LCT)Splay
板题，只放代码。
const int N = 3e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
…
Jayun 发布于 2023-11-14 21:40:39
00
K-D Tree (KDT)Rotating CalipersMonotonous StackBinary Heap
KDT 板子，但被卡了。
const int N = 4e5 + 5, K = 2;
const ll inf = 1e16;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c …
Jayun 发布于 2023-11-13 21:50:47
10
Virtual TreeDynamic Programming on Trees (Tree DP)Depth First Search (DFS)Binary Lifting
题意
$n$ 点树， $q$ 次询问，给 $m$ 个特殊点。树上每个点由最靠近它的特殊点控制，如果距离相同取编号小的。问每个特殊点控制多少点。
$n,q,\sum m\leq3\times10^5$ 。
题解
虚树。然后考虑树形 DP，从下往上扫一遍从上往下扫一遍。细节很多。
代码
const int N = 3e5 + 5, INF = 0x3f3f3f3f;
inline ll …
Jayun 发布于 2023-11-12 21:42:33
00
Virtual TreeDynamic Programming on Trees (Tree DP)Binary LiftingSimple Stack
题意
给定一棵树，多组询问，每组询问给定 $k$ 个点，你可以删掉不同于那 $k$ 个点的 $m$ 个点，使得这 $k$ 个点两两不连通，要求最小化 $m$ ，如果不可能输出 $-1$ 。询问之间独立。
$n,q,\sum k\leq10^5$
题解
特殊点作为关键点，将关键点按 $\mathrm{dfn}$ 排序，求出相邻点的最近公共祖先也作关键点，按照原树祖先后代关 …
Jayun 发布于 2023-11-12 20:44:28
00
2-SATStrongly Connected ComponentsTarjan
板。
const int N = 3e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while …
Jayun 发布于 2023-11-12 20:21:20
00
2-SATTarjanStrongly Connected Components
2-SAT 板子。
const int N = 2e6 + 10;
int n, m;
struct edge
{
int to, nxt;
}e[N << 1];
int head[N], tot;
void add (int u, int v)
{
e[++tot] = (edge){v, head[u]}, head[u] = tot;
}
int dfn[N], l …
Jayun 发布于 2023-11-12 19:46:47
00
Leftist TreeDisjoint Set
题解
并查集维护祖先，其余左偏树。
const int N = 1e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = ge …
Jayun 发布于 2023-11-12 17:48:32
00
Simple Segment TreeGreedyBinary HeapLinked List
题意
给定长 $n$ 的序列 $h_i$ ，每次操作可以使 $h_i\leftarrow h_i-1$ ， $q$ 次询问， 每次给出一个 $X$ , 求使用不超过 $X$ 次操作后 $\sum_{i=1}^{n-1}|h_i-h_{i+1}|+h_1+h_n$ 的最小值。
$n,q\leq5\times10^5,h_i\leq10^{12},X\leq10^{18}$ 。
…
Jayun 发布于 2023-11-11 15:17:49
00
Dynamic Programming on Ranges (Range DP)Linear Dynamic Programming (Linear DP)
题意
给定一个长 $n$ 的序列 $a_i$ ，可以进行操作，每次操作选区间 $[l,r]$ ，条件是 $\wedge_{i=l}^{r}~a_i=0$ ，操作完会删除 $[l,r]$ 。问最多操作次数。
$n,a_i\lt64$ 。
题解
区间 DP。设 $f_{l,r}$ 表示若区间 $[l,r]$ 可以合法，它的最大值，考虑 $l<k_1\leq k_2< …
Jayun 发布于 2023-11-11 15:01:40
00
CDQ's Divide-and-conquerBinary Indexed Tree (BIT)
题意
有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 且 $j \ne i$ 的 $j$ 的数量。 对于 $d \in [0, n)$ ，求 $f(i) = d$ 的数量。
$1 \leq n \l …
Jayun 发布于 2023-11-11 07:25:02
00