ui设计好就业吗_广州做网站最好的公司_百度广告客服电话_今天新闻

前言

之所以把闵可夫斯基和与 $slopetrick$ 放在一起是因为它们都是用来 维护凸包形态 的。

但是解决的问题却有着本质不同：

闵可夫斯基和主要用来优化转移式带 $(\min ,+),(\max ,+)$ 卷积的 $dp$。

而 $slopetrick$ 更像是一种更 简洁有效，适合在较特殊的修改凸包操作下维护凸包形态的 $trick$。也因此 $slopetrick$ 的题代码一般比较简短，但是思路也更加巧妙。

闵可夫斯基和优化 $dp$

算法

一般可以用闵可夫斯基和优化 $(\max ,+)$ 卷积或 $(\min ,+)$ 卷积的 $dp$ 转移。
有重要结论：

• 两个下凸的数组做 $(\min ,+)$ 卷积仍然得到下凸的数组。
• 两个上凸的数组做 $(\max ,+)$ 卷积仍然得到上凸的数组。

以下凸为例。
设 $f,g$ 为两个下凸的 $dp$ 数组，$h$ 是 $f,g$ 做 $(\min ,+)$ 卷积后的结果：
$h_i=\underset{j\le i}{\min }{f}_j+g_{i-j}$
那么 将 $f$ 和 $g$ 的差分数组归并就得到了 $h$ 的差分数组。

一般的归并方式是：$h_0=f_0+g_0$，剩下的差分数组从小到大归并到一起。

如果 $dp$ 数组的起点不是 $0$ 怎么办？
假设 $f,g$ 的起点分别是 $x,y$，那么有 $h_{x+y}=f_x+g_y$，剩下的差分数组跟原来一样归并到 $x+y$ 的后边。

因为涉及到两个集合的归并，因此闵可夫斯基和通常和 启发式 / 线段树合并 或 序列分治 一起使用以保证复杂度。

练习题

树上DS维护差分数组

[QOJ5421] Factories Once More

给定一棵 $n$ 个点的树，边无向有边权。你需要选出恰好 $k$ 个点，使得这 $k$ 个点的两两距离之和最大。
树上两个点的距离定义为这两个点之间简单路径的边权和。

$1\le k\le n\le 10^5$。

分析：
首先 $wqs$ 二分肯定是没法做的，因为每一个点的代价还跟选择了多少个点有关。对 $wqs$ 二分而言，开了几段/选了多少个点不能够影响贡献。

来考虑一个暴力的 $dp$：
首先第一步是把贡献拆到每条边上。
设 $d{p}_{x,i}$ 表示 $x$ 的子树里面选了 $i$ 个点，$x$ 子树里所有边的贡献之和的最大值。
对于点 $x$ 而言，设 $v$ 为它的儿子，$w$ 为 $(x,v)$ 的边权。转移分两步：

1. $d{p}_{v,i}\leftarrow d{p}_{v,i}+w\times i\times (k-i)$
2. $d{p}_{x,i+j}\leftarrow d{p}_{x,i}+d{p}_{v,j}$

那么第一步就是 $dp$ 数组加一个开口向下的二次函数。第二步是树背包，相当于对两个数组做 $(\max ,+)$ 卷积。
归纳法 证明 $d{p}_{x,i}$ 是关于 $i$ 的上凸函数：

1. 对于叶子显然成立
2. 假设对 $x$ 它的所有儿子都满足， 那么加二次函数后仍然是上凸函数，上凸函数做 $(\max ,+)$ 卷积仍然得到上凸函数。因此 $d{p}_x$ 上凸

那么就可以用闵可夫斯基和的结论优化转移了。
用 平衡树 维护每个 $d{p}_x$ 的差分数组。对于第一步，相当于差分数组加一条直线，那么维护直线的 $k,b$ 信息，懒标记下传即可。对于第二步，可以平衡树有交并，也可以直接启发式合并：将小的暴力插到大的里面。下面写的是启发式合并。

复杂度 $O(n\times {\log }_2^{2}n)$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
mt19937_64 rnd(153);
namespace FHQ {int root[N], rt1, rt2, rt3, tot;int rk;LL ans[N];vector< int > bin;struct node {int son[2];int sz;LL k, b, v, w;}t[N];int newnode(LL v) {int p = -1;if(!bin.empty()) p = bin.back(), bin.pop_back();if(p == -1) p = ++ tot;t[p] = (node) {{0, 0}, 1, 0, 0, v, rnd()};return p;}void Add(int p, LL k, LL b) {t[p].v += k * (t[t[p].son[0]].sz + 1) + b;t[p].k += k; t[p].b += b;}void spread(int p) {if(t[p].son[0]) Add(t[p].son[0], t[p].k, t[p].b);if(t[p].son[1]) Add(t[p].son[1], t[p].k, t[p].b + t[p].k * (t[t[p].son[0]].sz + 1));t[p].k = t[p].b = 0;}void update(int p) {t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;}void split(int p, LL lim, int &x, int &y) {if(!p) {x = y = 0; return ;}spread(p);if(t[p].v <= lim) y = p, split(t[p].son[0], lim, x, t[p].son[0]);else x = p, split(t[p].son[1], lim, t[p].son[1], y);update(p);}int Merge(int p, int q) {spread(p); spread(q);if(!p || !q) return p ^ q;if(t[p].w <= t[q].w) {t[p].son[1] = Merge(t[p].son[1], q);update(p);return p;}else {t[q].son[0] = Merge(p, t[q].son[0]);update(q);return q;}}void ins(int x, LL v) {split(root[x], v, rt1, rt2);root[x] = Merge(rt1, Merge(newnode(v), rt2));}void Swap(int x, int y) {swap(root[x], root[y]);}void del(int x) { // 删掉它的 root spread(root[x]);bin.pb(root[x]);root[x] = Merge(t[root[x]].son[0], t[root[x]].son[1]); }void change(int x, LL k, LL b) { // 整体加直线 Add(root[x], k, b);}void dfs(int p) {if(!p) return ;spread(p);dfs(t[p].son[0]);ans[++ rk] = t[p].v;dfs(t[p].son[1]);}LL ask(int x, int k) {int p = root[x];rk = 0;dfs(p);for(int i = 2; i <= rk; i ++ ) ans[i] += ans[i - 1];return ans[k];}
}
int n, K;
struct edge {int v, last;LL w;
}E[N * 2];
int head[N], tot, sz[N], big[N];
void add(int u, int v, LL w) {E[++ tot] = (edge) {v, head[u], w};head[u] = tot;
}
void dfs(int x, int fa) {sz[x] = 1;for(int i = head[x]; i; i = E[i].last) {int v = E[i].v; LL w = E[i].w;if(v == fa) continue;dfs(v, x); sz[x] += sz[v];if(sz[v] > sz[big[x]]) big[x] = v;    	FHQ::change(v, -2LL * w, w * (K + 1));}FHQ::Swap(x, big[x]);for(int i = head[x]; i; i = E[i].last) {int v = E[i].v; LL w = E[i].w;if(v == fa || v == big[x]) continue;while(FHQ::root[v]) {FHQ::ins(x, FHQ::t[FHQ::root[v]].v);FHQ::del(v);}}FHQ::ins(x, 0); // 插入一个点 
}
int main() {scanf("%d%d", &n, &K);for(int i = 1; i < n; i ++ ) {int u, v; LL w; scanf("%d%d%lld", &u, &v, &w);add(u, v, w); add(v, u, w);}dfs(1, 0);cout << FHQ::ask(1, K) << endl;return 0;
}

P9962 [THUPC 2024 初赛] 一棵树

给定一棵 $n$ 个点的树，最初每个点都是白色，你需要将恰好 $k$ 个点染成黑色。
定义一条边的权值是，断开这条边之后，两个连通块的黑色节点个数之差，定义一棵树的权值为所有边的权值求和，你需要最小化整棵树的权值。

$1\le k\le n\le 5\times 10^5$。

分析：
跟上边那道题差不多，不过第一步操作变成了加一个 绝对值函数。
特别维护 $0$ 的 $dp$ 值，第一步变成了区间加。平衡树也能维护，时间复杂度 $O(n{\log }_2^{2}n)$
由于每次区间加的分界点是定的，可以维护左右堆分别打标记，合并可以用 可并堆 维护，时间复杂度 $O(n\log n)$。
下面写的还是平衡树版本：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
mt19937_64 rnd(time(0));
int n, K, big[N], sz[N];
vector< int > E[N];
namespace FHQ {int root[N], rt1, rt2, rt3, tot;int idc;LL sv[N], ans[N]; // 初始值 vector< int > bin;struct node {int son[2];int sz, tag, v;LL w;}t[N * 2];inline int newnode(int v) {int p = -1;if(!bin.empty()) p = bin.back(), bin.pop_back();if(p == -1) p = ++ tot;t[p] = (node) {{0, 0}, 1, 0, v, rnd()};return p;}inline void update(int p) {t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;}inline void Add(int p, int c) {if(!p) return ;t[p].v += c; t[p].tag += c;}inline void spread(int p) {if(t[p].tag) {Add(t[p].son[0], t[p].tag);Add(t[p].son[1], t[p].tag);t[p].tag = 0;}}void Sps(int p, int lim, int &x, int &y) {if(!p) {x = y = 0; return ;}spread(p);if(t[t[p].son[0]].sz + 1 <= lim) x = p, Sps(t[p].son[1], lim - (t[t[p].son[0]].sz + 1), t[p].son[1], y);else y = p, Sps(t[p].son[0], lim, x, t[p].son[0]);update(p);}void Spv(int p, int lim, int &x, int &y) {if(!p) {x = y = 0; return ;}spread(p);if(t[p].v <= lim) x = p, Spv(t[p].son[1], lim, t[p].son[1], y);else y = p, Spv(t[p].son[0], lim, x, t[p].son[0]);update(p);}int Merge(int p, int q) { if(!p || !q) return p ^ q;spread(p); spread(q);if(t[p].w <= t[q].w) {t[p].son[1] = Merge(t[p].son[1], q);update(p);return p;}else {t[q].son[0] = Merge(p, t[q].son[0]);update(q);return q;}}void dfs(int x) {if(!x) return ;spread(x);dfs(t[x].son[0]);ans[++ idc] = t[x].v;dfs(t[x].son[1]);}inline LL ask(int x, int k) {idc = 0;dfs(root[x]);ans[0] = sv[x];for(int i = 1; i <= idc; i ++ ) ans[i] += ans[i - 1];return ans[k];}inline void ins(int x, int v) {Spv(root[x], v, rt1, rt2);root[x] = Merge(Merge(rt1, newnode(v)), rt2);}void del(int x) {if(!x) return ;bin.pb(x);del(t[x].son[0]);del(t[x].son[1]);}inline void change(int x) {Sps(root[x], K / 2, rt1, rt2);Add(rt1, -2); if(K & 1) {Sps(rt2, 1, rt2, rt3);Add(rt2, 0); Add(rt3, 2);rt2 = Merge(rt2, rt3);}else Add(rt2, 2);root[x] = Merge(rt1, rt2);sv[x] += K;}inline void Swap(int x, int y) {swap(root[x], root[y]); sv[x] = sv[y];}inline void Mg(int x, int y) {sv[x] += sv[y];idc = 0; dfs(root[y]);for(int i = 1; i <= idc; i ++ ) ins(x, ans[i]);del(root[y]);}
}
void dfs(int x, int fa) {sz[x] = 1;for(auto v : E[x]) {if(v == fa) continue;dfs(v, x); sz[x] += sz[v];if(sz[v] > sz[big[x]]) big[x] = v;FHQ::change(v);}FHQ::Swap(x, big[x]);for(auto v : E[x]) {if(v == fa || v == big[x]) continue;FHQ::Mg(x, v);}FHQ::ins(x, 0);
}
int main() {fin >> n >> K;for(int i = 1; i < n; i ++ ) {int u, v; fin >> u >> v;E[u].pb(v); E[v].pb(u);}dfs(1, 0);fout << FHQ::ask(1, K);return 0;
}

序列分治维护凸包

Gym103202 Forged in the Barrens

给定一个长度为 $n$ 的序列 { a i } \{a_i\} {ai​}，你需要对 $k=1,2,...,n$ 分别求出把序列划分成 $k$ 段，每段价值之和的最大值。
定义一段的价值为段内数字的极差。

$1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。

分析：
因为要对每个 $k$ 都求答案，因此不能 $wqs$ 二分。
有暴力 $dp$ 是设 $d{p}_{i,j}$ 表示前 $i$ 个数划分成 $j$ 段，但是没有什么前途。
考虑到 极差 是区间内的最大差值，相当于要求最大的最大和，那么可以任意钦定一段内的两个数的差提供价值，最优情况一定能转移到。
因此设 $d{p}_{i,j,0/1/2/3}$ 表示考虑了前 $i$ 个数，当前已经划分了 $j$ 段，当前段内 没有钦定最大值最小值 / 已经钦定了最小值没钦定最大值 / 已经钦定了最大值没钦定最小值 / 最大值最小值都已经钦定 的最优值。

转移可以以 $i$ 为顺序，但是没什么前途。
考虑按照线段树的结构分治序列，然后每一层把左右两个节点的状态合并，这样做的原因是可以让转移变成 $(\max ,+)$ 卷积的形式。

那么状态变成了 $d{p}_{p,j,x_1,x_2}$ 表示 $p$ 节点内划分了 $j$ 段，左右两个边界的半段分别是 x 1 , x 2 ( x 1 , x 2 ∈ { 0 , 1 , 2 } ) x_1,x_2(x_1,x_2 \in \{0,1,2\}) x1​,x2​(x1​,x2​∈{0,1,2}) 的最优值。

然后是可以感受到 $d{p}_{p,j,x_1,x_2}$ 关于 $j$ 上凸，因此可以闵可夫斯基和优化。
设 $p$ 的两个儿子分别为 $l{s}_p$ 和 $r{s}_p$，在 $p$ 处合并就是分别枚举 $l{s}_p$ 和 $r{s}_p$ 在第三第四维的状态归并，然后对 $p$ 转移到的状态按位取 $\max$。

这里的转移需要详细说一下：

(⭐) 首先划分成 $j$ 段的含义可以理解为选出 $j$ 个不交段，有的元素即使没有划分到某一段中也没关系，因为可以把它们任意分到相邻段里答案不会变劣。说这个的原因是因为下面的转移可能会出现某些元素没有被分到一段的情况。

一. 对于边界只有一个点的情况，如何赋初始值呢？
用 $[...]$ 表示一段，用 O 表示一个元素。
分以下三种情况：

其中第二维表示段数，简洁的写法可以开一个 $vector$ 存 $dp$ 值：$d{p}_{p,x_1,x_2}$ 里的第 $i$ 个元素就是 $d{p}_{p,i,x_1,x_2}$。

假设枚举到的状态为 $d{p}_{l{s}_p,a,b}$ 和 $d{p}_{r{s}_p,c,d}$，有以下两种情况需要转移：

①.两段的左右边界合成一段

1. $b=0,c=0$。有可能边界段都为空，也有可能存在边界段但是没有钦定最大最小值。认为此时两侧边界不存在， $d{p}_{p,a,d}\leftarrow d{p}_{l{s}_p,a,b}\oplus d{p}_{r{s}_p,c,d}$。这里 $\oplus$ 是 $(\max ,+)$ 卷积。
2. $b=1,c=2$ 或 $b=2,c=1$。此时认为中间段新开，因此将左右儿子的 $dp$ 数组卷积后要整体平移一位，$0$ 的位置补 $-\infty$。

②.有一段完全被包含
比如右段完全包含在左段的右边界里，那么不难发现更新得到的右边界段最多包含一个极值，因为如果包含两个极值那么可以将这两个极值为边界的区间选出来作为一段。
所以有转移：
$d{p}_{p,a,b}\leftarrow d{p}_{l{s}_p,a,0}+g_{r{s}_p,b}$
$d{p}_{p,a,b}\leftarrow d{p}_{l{s}_p,a,b}+g_{r{s}_p,0}$

$g_{p,x}$ 的含义是 $p$ 对应的区间 没选极值/选出最大值/最小值 的最优值。
那么这样就转移完了。

还有一个问题：
众所周知：对上凸函数取 $min$ 得到上凸函数， 对下凸函数取 $max$ 得到下凸函数。
但是对于 $d{p}_{p,a,b}$ 是对多个上凸函数每位取 $max$ 的结果，那么 $d{p}_{p,a,b}$ 还是上凸函数吗？
解释是我们开始就按照另一种方式证明了它的凸性，因此不用担心它不是上凸的。

由于每次归并的复杂度是基于区间长度的，因此时间复杂度等于所有分治区间的长度和，为 $O(n\log n)$。

CODE：

// 分治， 然后闵可夫斯基和 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
const LL INF = 1e18;
vector< LL > dp[N * 4][3][3]; // dp 是有分界线的  0 表示啥也没钦定, 1表示钦定了最小值， 2 表示钦定了最大值 
vector< LL > f[3][3];
LL g[N * 4][3], ans[N]; // g 是连在一起的 
int n, a[N];
vector< LL > add(vector< LL > A, LL x) {for(int i = 0; i < A.size(); i ++ ) A[i] += x;return A; 
}
vector< LL > mg(vector< LL > A, vector< LL > B, int k) { // 合并两个凸包  k 是偏移量 vector< LL > C; if(A.empty() || B.empty()) return C;if(k == 1) C.pb(-INF);C.pb(A[0] + B[0]);int p = 1, q = 1;while(p < A.size() && q < B.size()) {if(A[p] - A[p - 1] > B[q] - B[q - 1]) C.pb(A[p] - A[p - 1]), p ++;else C.pb(B[q] - B[q - 1]), q ++;}while(p < A.size()) C.pb(A[p] - A[p - 1]), p ++;while(q < B.size()) C.pb(B[q] - B[q - 1]), q ++;for(int i = k + 1; i < C.size(); i ++ ) C[i] += C[i - 1];return C;
}
vector< LL > Max(vector< LL > A, vector< LL > B) {for(int i = 0; i < B.size(); i ++ ) {if(A.size() <= i) A.pb(B[i]);else A[i] = max(A[i], B[i]);}return A;
}
void solve(int p, int l, int r) {if(l == r) {for(int i = 0; i < 3; i ++ ) {for(int j = 0; j < 3; j ++ ) {if(i != 0 && j != 0) continue;if(i == 0 && j == 0) dp[p][i][j].pb(0), dp[p][i][j].pb(0); // 开几段都是 0else if(max(i, j) == 1) dp[p][i][j].pb(-a[l]);else dp[p][i][j].pb(a[l]);}if(i == 0) g[p][i] = 0;else if(i == 1) g[p][i] = -a[l];else g[p][i] = a[l];}return ;}int mid = (l + r >> 1);solve(p << 1, l, mid);solve(p << 1 | 1, mid + 1, r);for(int i = 0; i < 3; i ++ ) for(int j = 0; j < 3; j ++ ) {vector< LL > tmp; swap(tmp, f[i][j]);}for(int a = 0; a < 3; a ++ ) {for(int d = 0; d < 3; d ++ ) {f[a][d] = Max(Max(f[a][d], mg(dp[p << 1][a][0], dp[p << 1 | 1][0][d], 0)), Max(mg(dp[p << 1][a][2], dp[p << 1 | 1][1][d], 1), mg(dp[p << 1][a][1], dp[p << 1 | 1][2][d], 1)));}}for(int x = 0; x < 3; x ++ ) {for(int t = 0; t < 3; t ++ ) {vector< LL > h;h = add(dp[p << 1][x][0], g[p << 1 | 1][t]);f[x][t] = Max(f[x][t], h); f[x][t] = Max(f[x][t], dp[p << 1][x][t]);h = add(dp[p << 1 | 1][0][x], g[p << 1][t]);f[t][x] = Max(f[t][x], h); f[t][x] = Max(f[t][x], dp[p << 1 | 1][t][x]);}}for(int i = 0; i < 3; i ++ ) for(int j = 0; j < 3; j ++ ) dp[p][i][j] = f[i][j];for(int i = 0; i < 3; i ++ ) g[p][i] = max(g[p << 1][0] + g[p << 1 | 1][i], g[p << 1 | 1][0] + g[p << 1][i]);
} 
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);solve(1, 1, n);for(int i = 1; i <= n; i ++ ) printf("%lld\n", dp[1][0][0][i]);return 0;
}

[ABC383G] Bar Cover

给你 $n$ 个数 { a i } \{a_i\} {ai​} 和正整数 $k$，对于 $i=1,2,...,\lfloor \frac{n}{k}\rfloor$：
求出在这 $n$ 个数里选出 $i$ 个块，每个块长度为 $k$，并且块两两不重叠的最大块内数字和。

$1\le n\le 2\times 10^5$， $1\le k\le \min (n,5)$，$-10^9\le a_i\le 10^9$。

分析：
跟上一题差不多。
还是考虑序列分治，设 $d{p}_{p,a,b,i}$ 表示 $p$ 节点对应的区间选了 $i$ 个段，左边界段长度为 $a$，右边界段长度为 $b$ 的最优值。
那么边界情况为以下三种：

1. $]O[$
2. $][O$
3. $O][$

然后转移和上面差不多，甚至少了很多细节。
注意 $k=1$ 特殊处理一下。
复杂度也是一只 $log$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
const LL INF = 2e14;
int n, K;
LL a[N], ans[N], sum[N];
vector< LL > dp[N * 4][5][5]; // dp[i][j][k] 表示考虑了 i 节点， 左边段有 j 个， 右边段有 k 个的方案  
inline vector< LL > Mg(const vector< LL > f, const vector< LL > g, int d) {vector< LL > h;if(d == 1) h.pb(-INF);if(f.empty() || g.empty()) return h;h.pb(f[0] + g[0]);int p = 1, q = 1;while(p < f.size() && q < g.size()) {if(p < f.size() && f[p] - f[p - 1] >= g[q] - g[q - 1]) h.pb(f[p] - f[p - 1]), p ++;else h.pb(g[q] - g[q - 1]), q ++;}while(p < f.size()) h.pb(f[p] - f[p - 1]), p ++;while(q < g.size()) h.pb(g[q] - g[q - 1]), q ++;for(int i = d + 1; i < h.size(); i ++ ) h[i] += h[i - 1];return h;
}
inline void Max(vector< LL > &f, vector< LL > g) {if(f.size() < g.size()) swap(f, g);for(int i = 0; i < g.size(); i ++ ) f[i] = max(f[i], g[i]);
}
inline vector< LL > Add(vector< LL > f, LL c) {for(int i = 0; i < f.size(); i ++ ) f[i] += c;return f;
}
void solve(int p, int l, int r) {if(l == r) {if(K == 1) {dp[p][0][0].pb(0);dp[p][0][0].pb(a[l]); }else {	dp[p][0][0].pb(0);dp[p][1][0].pb(a[l]);dp[p][0][1].pb(a[l]); // 每次汇合再判断是否新开段 }return ;}int mid = (l + r >> 1);solve(p << 1, l, mid);solve(p << 1 | 1, mid + 1, r);for(int i = 0; i < K; i ++ ) {for(int j = 0; j < K; j ++ ) {for(int k = 0; k < K; k ++ ) {int t = (j == 0 ? 0 : K - j);Max(dp[p][i][k], Mg(dp[p << 1][i][j], dp[p << 1 | 1][t][k], j > 0));}}}for(int i = 0; i < K; i ++ ) for(int j = 0; j < K - (r - mid); j ++ ) Max(dp[p][i][j + r - mid], Add(dp[p << 1][i][j], sum[r] - sum[mid]));for(int i = 0; i < K; i ++ ) for(int j = 0; j < K - (mid - l + 1); j ++ ) Max(dp[p][j + mid - l + 1][i], Add(dp[p << 1 | 1][j][i], sum[mid] - sum[l - 1])); 
}
int main() {scanf("%d%d", &n, &K);for(int i = 1; i <= n; i ++ ) {scanf("%lld", &a[i]);sum[i] = sum[i - 1] + a[i];}solve(1, 1, n);for(int i = 1; i <= (n / K); i ++ ) printf("%lld ", dp[1][0][0][i]);return 0;
}

P11459 [USACO24DEC] It’s Mooin’ Time P

给你一个长度为 $n$ 的字符串，仅由 $M$ 和 $O$ 组成。对于字符串的每个位置 $i$，需要花费 $c_i$ 的代价将其修改为另一种字符。
给定常数 $L$，定义 魔力串 为一个 $M$ 后面跟了 $L-1$ 个 $O$。那么你需要对所有 $i=1,2,...,\lfloor \frac{n}{L}\rfloor$ 回答：
将字符串修改成至少包含 $i$ 个魔力串需要的最小花费。

$1\le n\le 3\times 10^5$， $1\le c_i\le 10^8$，$1\le L\le \min (n,3)$。

分析：
跟上一题同样没啥区别感觉，边界的三种情况也差不多。
规定左边界段都是 $O$，右边界段的第一个必须是 $M$，那么只需要记录边界段的长度即可。
这里有一个注意点是如果对每个结点都调用它的 $dp$ 数组，即使每次转移之后清空，但是空间已经开出来了所以还是占用空间，也就是空间复杂度 $O(n\log n)$，但是这样会 $MLE$。
考虑 垃圾回收 优化空间：考虑每个节点的对应的 $dp$ 数组编号都先从垃圾箱里找，如果没有就新建。对于那些不用的状态就放到垃圾箱里。那么发现每一层要多建一个编号，因此总共有 $\log n$ 个编号。那么考虑每个编号的 $vector$ 开了多大：发现最坏情况下是有 $1$ 个长度为 $n$，有两个长度为 $\frac{n}{2}$，有 $4$ 个长度为 $\frac{n}{4}$，…，因此总空间就是 $\sum _{i=0}^{2^i\le \log n}n=n\log \log n$。

时间复杂度 $O(n\log n)$。

CODE：

// 观察发现是凸的，这种对每个k都回答：可以分治闵可夫斯基和 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 3e5 + 10;
typedef long long LL;
const LL INF = 3e13;
int L, n, a[N];
char str[N];
LL c[N];
vector< LL > dp[N * 4][3][3]; // 左边只有 O， 右边含一个 M 
vector< int > bin;
int idx[N * 4], tot;
inline void Min(vector< LL > &f, vector< LL > g) {if(f.size() < g.size()) swap(f, g);for(int i = 0; i < g.size(); i ++ ) f[i] = min(f[i], g[i]); 
}
vector< LL > Mg(vector< LL > f, vector< LL > g, int d) {vector< LL > h;if(d == 1) h.pb(INF);if(f.empty() || g.empty()) return h;h.pb(f[0] + g[0]);int p = 1, q = 1;while(p < f.size() && q < g.size()) {if(f[p] - f[p - 1] < g[q] - g[q - 1]) h.pb(f[p] - f[p - 1]), p ++;else h.pb(g[q] - g[q - 1]), q ++;}while(p < f.size()) h.pb(f[p] - f[p - 1]), p ++;while(q < g.size()) h.pb(g[q] - g[q - 1]), q ++;for(int i = d + 1; i < h.size(); i ++ ) h[i] += h[i - 1];return h;
}
int build() {int p = -1;if(!bin.empty()) p = bin.back(), bin.pop_back();if(p == -1) p = ++ tot;for(int i = 0; i < L; i ++ ) for(int j = 0; j < L; j ++ ) dp[p][i][j].clear();return p;
}
void solve(int p, int l, int r) {idx[p] = build(); // 清空过了 if(l == r) {if(a[l] == 1) {dp[idx[p]][0][0].pb(0);if(L == 1) dp[idx[p]][0][0].pb(0);dp[idx[p]][0][1].pb(0);dp[idx[p]][1][0].pb(c[l]);}else {dp[idx[p]][0][0].pb(0);if(L == 1) dp[idx[p]][0][0].pb(c[l]);dp[idx[p]][1][0].pb(0);dp[idx[p]][0][1].pb(c[l]);}return ;}int mid = (l + r >> 1);solve(p << 1, l, mid); solve(p << 1 | 1, mid + 1, r);for(int i = 0; i < L; i ++ ) for(int j = 0; j < L; j ++ ) // 中间会合并 for(int k = 0; k < L; k ++ ) {Min(dp[idx[p]][i][j], Mg(dp[idx[p << 1]][i][k], dp[idx[p << 1 | 1]][k == 0 ? 0 : L - k][j], k > 0));}for(int i = 0; i < L; i ++ ) for(int j = 1; j < L - (r - mid); j ++ ) {vector< LL > tmp; LL w = 0;for(int k = mid + 1; k <= r; k ++ ) w += (a[k] == 0 ? 0 : c[k]);tmp.pb(w); Min(dp[idx[p]][i][j + r - mid], Mg(dp[idx[p << 1]][i][j], tmp, 0));}for(int i = 0; i < L; i ++ ) for(int j = 1; j < L - (mid - l + 1); j ++ ) {vector< LL > tmp; LL w = 0;for(int k = l; k <= mid; k ++ ) w += (a[k] == 0 ? 0 : c[k]);tmp.pb(w); Min(dp[idx[p]][j + mid - l + 1][i], Mg(dp[idx[p << 1 | 1]][j][i], tmp, 0));}bin.pb(idx[p << 1]); bin.pb(idx[p << 1 | 1]);
}
int main() {scanf("%d%d", &L, &n); scanf("%s", str + 1);for(int i = 1; i <= n; i ++ ) a[i] = (str[i] == 'M' ? 1 : 0);for(int i = 1; i <= n; i ++ ) scanf("%lld", &c[i]);solve(1, 1, n);for(int i = 1; i <= n / L; i ++ ) printf("%lld\n", dp[idx[1]][0][0][i]);return 0;
}

gym102331H Honorable Mention

给定长度为 $n$ 的序列 { a i } \{a_i\} {ai​}，$q$ 次询问，每次问你在 $[l,r]$ 区间中选出 $k$ 个不交的子区间，子区间里的数字之和的最大值。

$1\le n,q\le 35000$， $-35000\le a_i\le 35000$，$1\le k\le r-l+1$。

分析：
好牛的题。
发现是区间询问而非对全局回答，第一想法是建一棵线段树将区间拆成 $\log n$ 个节点，然后每次将这 $\log n$ 个节点做闵可夫斯基和。
但是归并的复杂度是区间长度，这样总复杂度是 $O(qn)$ 的。
考虑单次询问可以 $wqs$ 二分，但是做一遍 $dp$ 的复杂度也基于区间长度。

正解是将这两种做法结合：考虑 $wqs$ 二分，但是怎样快速的求出结果？发现可以将拆成的 $\log n$ 个节点的结果合并起来，对每个节点而言，由于已经维护好凸包了因此可以直接将直线与凸包的切点二分出来。
复杂度计算： $wqs$ 二分是 $\log V$，一共有 $\log n$ 个节点，每次二分切点复杂度 $\log n$，单次询问复杂度就是 $O(q\log V{\log }^{2}n)$。空间复杂度 $O(n\log n)$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
#define MP make_pair
using namespace std;
typedef long long LL;
const LL INF = 1e10;
typedef pair< LL, int > PII;
const int N = 36000;
int n, q;
LL a[N], sum[N], w[N * 4], L[N * 4], R[N * 4];
vector< LL > dp[N * 4][2][2]; // 0 代表没有， 1 代表有 
vector< int > node;
PII f[2], g[2];
inline void Max(vector< LL > &f, vector< LL > g) {if(f.size() < g.size()) swap(f, g);for(int i = 0; i < g.size(); i ++ ) f[i] = max(f[i], g[i]);
}
vector< LL > Mg(const vector< LL > f, const vector< LL > g, int d) {vector< LL > h;if(d == 1) h.pb(-INF);if(f.empty() || g.empty()) return h;h.pb(f[0] + g[0]);int p = 1, q = 1;while(p < f.size() && q < g.size()) {if(f[p] - f[p - 1] >= g[q] - g[q - 1]) h.pb(f[p] - f[p - 1]), p ++;else h.pb(g[q] - g[q - 1]), q ++;}while(p < f.size()) h.pb(f[p] - f[p - 1]), p ++;while(q < g.size()) h.pb(g[q] - g[q - 1]), q ++;for(int i = d + 1; i < h.size(); i ++ ) h[i] += h[i - 1];return h;
}
PII Add(PII x, PII y) {return MP(x.first + y.first, x.second + y.second);}
void build(int p, int l, int r) {w[p] = sum[r] - sum[l - 1];L[p] = l; R[p] = r;if(l == r) {dp[p][0][0].pb(0); dp[p][0][0].pb(a[l]);dp[p][0][1].pb(a[l]); dp[p][1][0].pb(a[l]);return ;}int mid = (l + r >> 1);build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);vector< LL > tmp;for(int i = 0; i <= 1; i ++ ) for(int j = 0; j <= 1; j ++ )for(int k = 0; k <= 1; k ++ ) for(int l = 0; l <= 1; l ++ )Max(dp[p][i][j], Mg(dp[p << 1][i][k], dp[p << 1 | 1][l][j], k + l > 0));tmp.clear(); tmp.pb(w[p << 1 | 1]);for(int i = 0; i <= 1; i ++ ) for(int j = 0; j <= 1; j ++ ) Max(dp[p][i][1], Mg(dp[p << 1][i][j], tmp, 0));tmp.clear(); tmp.pb(w[p << 1]);for(int i = 0; i <= 1; i ++ ) for(int j = 0; j <= 1; j ++ ) Max(dp[p][1][i], Mg(dp[p << 1 | 1][j][i], tmp, 0));return ;
}
void Find(int p, int lp, int rp, int l, int r) {if(l <= lp && r >= rp) {node.pb(p); return ;}int mid = (lp + rp >> 1);if(l <= mid) Find(p << 1, lp, mid, l, r);if(r > mid) Find(p << 1 | 1, mid + 1, rp, l, r);
}
void check(LL cost) { // 开一段的代价 f[0] = MP(0, 0); f[1] = MP(-INF, 0);g[0] = g[1] = MP(-INF, -INF);for(auto p : node) { // 在 p 上二分 for(int i = 0; i <= 1; i ++ ) { // 枚举状态 for(int j = 0; j <= 1; j ++ ) {int sz = dp[p][i][j].size();int l = 0, r = sz - 1, mid, res = min(0, sz - 1);while(l <= r) {mid = (l + r >> 1);if(mid == sz - 1 || dp[p][i][j][mid + 1] - dp[p][i][j][mid] < cost) res = mid, r = mid - 1;else l = mid + 1;}if(res != -1) { // 不是 -1 再转移 PII v = MP(dp[p][i][j][res] - cost * res, res);if(i == 0) g[j] = max({g[j], Add(f[0], v), Add(f[1], MP(v.first - cost, v.second + 1))});else g[j] = max(g[j], Add(max(f[0], f[1]), MP(v.first - cost, v.second + 1)));}}}PII v = MP(w[p], 0);g[1] = max(g[1], Add(max(f[0], f[1]), v));f[0] = g[0]; f[1] = g[1];g[0] = g[1] = MP(-INF, -INF);}
} 
LL calc(int l, int r, int k) {node.clear(); Find(1, 1, n, l, r); // 找到 log 个节点 LL ll = -1225000000, rr = 1225000000, mid, res;while(ll <= rr) {mid = (ll + rr >> 1);check(mid);PII ans = f[0]; if(ans.second == k) return ans.first + mid * k;else if(ans.second > k) res = mid, ll = mid + 1;else rr = mid - 1;}check(res);PII ans = f[0];return ans.first + res * k;
}
int main() {scanf("%d%d", &n, &q);for(int i = 1; i <= n; i ++ ) {scanf("%lld", &a[i]);sum[i] = sum[i - 1] + a[i];}build(1, 1, n);for(int i = 1; i <= q; i ++ ) {int l, r, k; scanf("%d%d%d", &l, &r, &k);printf("%lld\n", calc(l, r, k));}return 0;
}

树上分治维护凸包

gym102331J Jiry Matchings

给你一棵 $n$ 个点的无向树，边有边权。你需要对每个 $i=1,2,...,n-1$ 回答：

如果存在 $i$ 条边的匹配，那么选中的 $i$ 条边的边权之和的最大值是多少。

$2\le n\le 2\times 10^5$，$-10^9\le w_i\le 10^9$。

分析：
好牛的题。
首先可以想到一个 $dp$：$d{p}_{i,0/1,j}$ 表示考虑了以 $i$ 为根的子树， $i$ 是否在一个匹配里，子树中选了 $j$ 个匹配的最大值。
那么容易证明 $d{p}_{i,0/1}$ 是关于 $j$ 的上凸函数：肯定先选大的再选小的，过程和费用流类似。
转移是两个背包做 $(\max ,+)$ 卷积，然后需要每位取 $\max$ 更新。
但是这样复杂度是不对的，因为涉及到每位取 $\max$，那么需要遍历整个 $dp$ 数组。
考虑序列上可以支持对位取 $\max$ 是因为 分治的 $dp$ 数组大小等于区间长度，但是树上却不是。
怎么把树往序列上靠拢呢？想到 树剖。
把树剖成若干条重链，对于一个点 $x$ 而言：

1. 首先将 $x$ 的所有轻儿子的 $dp$ 数组 分治归并，意思就是把轻儿子的编号排成一行然后想序列分治那样倍增归并两边。然后按位取 $\max$，并将得到的 $dp$ 数组赋给 $x$
2. 如果 $x$ 是一条重链的链头，那么对这条重链做一遍类似序列分治的归并。将得到的 $dp$ 数组放到链头。

复杂度分析：
考虑一个元素会被枚举多少次：
对于 $1$ 而言，发现它会在祖先链上的每一条轻边被遍历 $\log n$ 次。总共有 $\log n$ 条轻边，因此 $1$ 的总复杂度为 $O(n{\log }^{2}n)$。
对于 $2$ 而言，发现它的祖先链上每出现一条轻边，他就会进入到一条重链中。在每条重链被枚举到的次数为 $\log n$，一共会进入 $\log n$ 条重链，因此 $2$ 的总复杂度为 $O(n{\log }^{2}n)$。
总复杂度 $O(n{\log }^{2}n)$。代码还没写。

$Slopetrick$

算法

$slopetrick$ 是一种优化 $dp$ 的方法，一般应用于 $dp$ 数组是凸包的情况。核心思路是通过 存储 $dp$ 数组的一些关键信息（如分段函数的分段点/最左边直线的信息）来维护凸包，通过 打标记，增删关键点 的方式维护凸包的变化，从而高效完成转移。

一般可以使用 $slopetrick$ 优化的 $dp$ 方程有以下要求：

• $dp$ 数组是一个凸包
• $dp$ 数组是分段的 一次函数 且是连续的。

分段一次凸函数具有很好的性质：

• 两个凸函数相加还是凸函数。
  设凸函数分别为 $F_i$ 和 $G_i$，相加得到 $H_i=F_i+G_i$。那么设 $N_F$ 为 $F$ 的分段点集合， $N_G$ 为 $G$ 的分段点集合，最左边的直线分别为 $y_f=k_{f}x+b_f$ 和 $y_g=k_{g}x+b_g$。那么有 $N_H=N_F\cup N_G$，$y_h=(k_f+k_g)x+(b_f+b_g)$。
• 一次函数既可以看作上凸函数也可看作下凸函数，因此凸函数加一次函数仍为凸函数。

可以将分段一次函数每次斜率变化 $1$ 的点加入数据结构中，如果在一个点上的斜率变化量大于 $1$ 就加入若干个这个点。
比如函数
$$y=\{\begin{array}{cc}x+5& x\le 1\\ 6& 1<x\le 7\\ -2x+13& x>7\end{array}$$

图像为

那么维护最左侧直线为 $y=x+5$，分段点集合为 { 1 , 7 , 7 } \{1,7,7\} {1,7,7}。

再比如绝对值函数 $y=|x-a|$ 的分段点集合为 { a , a } \{a, a\} {a,a}，最左侧直线为 $y=-x+a$。

这样就能比较优美的维护一些操作：

以上凸包为例：

• 相加
  将最左侧直线相加，将分段点合并。

• 找最大值/最小值
  就是斜率为 $0$ 那一段的函数值。一般开左右两个堆 $L,R$ 分别维护斜率为正和斜率为负的分段点，左堆开成大根堆，右堆开成小根堆。那么两个堆顶之间的区域就是极值段。

• 加一次函数
  比如加 $y=x+b$。那么首先将左侧直线的信息相加，然后将右堆的堆顶放到左堆里。
  如果加入一次函数的斜率比较大，那么会导致插入的分界点数量很多。此时为了保证复杂度将分段点的信息用二元组 $(x,k)$ 表示，其中 $k$ 表示斜率的变化量（也可理解成斜率的差分）。

• 加绝对值函数
  实际上就是两个凸包相加的特殊情况，按照第一种操作维护即可。可能涉及将一个堆的堆顶移到另一个堆中。

• 取前后缀 $\max$
  如果是取前缀 $\max$ 就是扔掉右堆的所有点，取后缀 $\max$ 就是扔掉左堆的所有点。

• 平移
  改变最左侧直线信息，给某个堆的分段点打上平移标记。

• 翻转
  改变最左侧直线信息，给某个堆的分段点打上翻转标记。

• 统计答案
  一般答案都是函数极值，维护方式有两种：
  1 每次加函数时维护极值的变化。
  2 从最左边开始还原图像。

练习题

CF713C Sonya and Problem Wihtout a Legend

给定一个有 $n$ 个正整数的数组，一次操作中，可以把任意一个元素加一或减一。（元素可被减至负数或 0），求使得原序列严格递增的求最小操作次数。

$1\le n\le 3000$， $1\le a_i\le 10^9$。

分析：
首先把第 $i$ 个元素减去 $i$，那么问题变成了使原序列单调不降的最小操作次数。
那么有一个基于 值域 的 $dp$：
$d{p}_{i,v}$ 表示考虑了前 $i$ 个数使它们单调不降，并且把第 $i$ 个数变成 $v$ 的最小操作数。
那么有转移： $d{p}_{i,v}\leftarrow \underset{v^{\prime }\le v}{\min }d{p}_{i-1,v^{\prime }}+|a_i-v|$。
把它分成两步：
$d{p}_{i,v}\leftarrow \underset{v^{\prime }\le v}{\min }d{p}_{i-1,v^{\prime }}$
$d{p}_{i,v}\leftarrow d{p}_{i,v}+|a_i-v|$

感性猜测 $d{p}_{i,v}$ 是关于 $v$ 的下凸函数，下面用 归纳法 证明：

1. $d{p}_{1,v}=|a_i-v|$，显然下凸。
2. 假设 $d{p}_{i-1}$ 下凸，那么转移相当于先把凸包最小值右边的部分推平，然后加上一个绝对值函数。我们知道下凸函数加下凸函数得到的还是下凸函数。因此 $d{p}_i$ 下凸。

那么考虑用 $slopetirck$ 维护：
开左右两个堆 $L,R$ 维护斜率变化点，其中左边是斜率小于 $0$ 的，右侧是斜率大于 $0$ 的，两个堆顶之间是最小值。
求前缀最小值：将右堆清空。
加 $y=|a_i-v|$：分两种情况讨论，当 $v>L.top()$ 时，由于右边已经推平了，因此对答案没影响，将一个 $v$ 插入左堆，一个 $v$ 插入右堆。当 $v<L.top()$ 时，答案的增量为 $L.top()-v$，$v$ 左侧的变化点斜率减 $1$，右侧的加 $1$，因此往左堆插入两个 $v$，将左堆的堆顶移到右堆中。

观察到右堆的信息实际上没有用的，因此只维护左堆即可。复杂度 $O(n\log n)$。
代码非常简单：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
priority_queue< int > q;
LL ans;
int main() {int n; scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {int x; scanf("%d", &x);x -= i;q.push(x);if(x < q.top()) {q.push(x);ans += q.top() - x;q.pop();}}cout << ans << endl;return 0;
}

[ABC217H] Snuketoon

有一个游戏，发生在发生在一条数轴上，最初 0 时刻，Snuke 在 0 号节点。
每过一个时刻，你可以选择向正方向或负方向移动一格，或者不移动。
接下来有 n 个事件，每一个事件用 $T_i,D_i,X_i$ 描述，其中 $T_i$ 表示事件发生时刻，假设 Snuke 此时在 $p$ 点：

1. 若 $D_i=0$，则 Snuke 受到 max ⁡ { 0 , X i − p } \max\{0, X_i - p\} max{0,Xi​−p} 的伤害。
2. 若 $D_i=1$，则 Snuke 受到 max ⁡ { 0 , p − X i } \max\{0, p - X_i\} max{0,p−Xi​} 的伤害。

问 $n$ 次事件后 Sunke 受到的伤害之和的最小值。

$1\le n\le 2\times 10^5$， $1\le T_1\le T2\le ...\le T_n\le 10^9$， $-10^9\le X_i\le 10^9$。

分析：
首先有一个暴力的 $dp$：设 $d{p}_{i,j}$ 表示 $T_i$ 时刻时位置在 $j$ 的最小受伤量。那么有转移：
$$d{p}_{i,j}\leftarrow \underset{|j-k|\le T_i-T_{i-1}}{\min }d{p}_{i-1,k}+\{\begin{array}{cc}\max (0,X_i-j)& D_i=0\\ \max (0,j-X_i)& D_i=1\end{array}$$

还是分两步转移：

$d{p}_{i,j}\leftarrow \underset{|j-k|\le T_i-T_{i-1}}{\min }d{p}_{i-1,k}$

$d{p}_{i,j}\leftarrow d{p}_{i,j}+\{\begin{array}{cc}\max (0,X_i-j)& D_i=0\\ \max (0,j-X_i)& D_i=1\end{array}$

可以感性猜想 $d{p}_i$ 关于 $j$ 是下凸的，下面用归纳法证明：

1. 每次的取 $\min$ 操作相当于把下凸包的极小值区间左右两边各自平移 $T_i-T_{i-1}$ 个单位，不改变凸包的形态。
2. 第二步加的函数是一段一次函数加一段 $0$，显然下凸。

因此 $d{p}_i$ 下凸，那么考虑用 $slopetrick$ 维护凸包形态：

第一步转移：只需要给左右两个堆打平移标记即可。
第二步转移：假设是 $D_i=0$ 的情况，另一种类似。发现是一段斜率为 $-1$ 的一次函数，然后与一段 $0$ 拼起来。当 $X_i<R.top()$ 时，对最小值没有影响，只需要把 $X_i$ 插到坐堆里。当 $X_i>R.top()$ ，那么最小值会增大 $X_i-R.top()$，并且 $X_i$ 左侧的点斜率减 $1$，右侧点斜率不变，因此将 $X_i$ 插入右堆中，将右堆堆顶移到左堆里。

时间复杂度 $O(n\log n)$。
CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
const LL INF = 2e14;
priority_queue< LL, vector< LL >, greater< LL > > qr; // 小根堆
priority_queue< LL, vector< LL >, less< LL > > ql; // 大根堆
LL tagl, tagr, L, R; 
int n;
int main() {ql.push(0); qr.push(0);L = R = 0; // 左右边界 scanf("%d", &n);LL lt = 0, ans = 0;for(int i = 1; i <= n; i ++ ) {LL T, X; int D; scanf("%lld%d%lld", &T, &D, &X);// 第一步， 左右平移 T - lttagl -= T - lt; tagr += T - lt;L -= T - lt; R += T - lt;// 第二步， 插入一条斜率为 +1 或 -1 的直线if(D == 0) { if(X <= L) ;else {LL r = qr.top() + tagr;if(X <= r) ql.push(X - tagl);else {LL b = max(X - R, 0LL); X = min(X, R);ans += (X - r) + b;qr.pop(); ql.push(r - tagl); qr.push(X - tagr);}}} else {if(X >= R) ;else {	LL l = ql.top() + tagl;if(X >= l) qr.push(X - tagr);else {LL b = max(L - X, 0LL); X = max(X, L);ans += (l - X) + b;ql.pop(); qr.push(l - tagr); ql.push(X - tagl);}}}lt = T;}printf("%lld\n", ans);return 0;
}

CF1534G A New Beginning

你在一个二维平面直角坐标系的原点 $(0,0)$ 上，你可以向上或向右移动 $1$ 单位长度任意次。
现在给你 $n$ 个点，第 $i$ 个点为 $(x_i,y_i)$。你需要对这 $n$ 个点都打上标记。具体的，在任意时刻，如果你在点 $(X,Y)$ 并希望对点 $(x,y)$ 打标记，你需要花费 $\max (|X-x|,|Y-y|)$ 单位能量。
求最少花费多少单位能量。

$1\le n\le 8\times 10^5$，$0\le x_i,y_i\le 10^9$。

分析：
这题属于那种第一步很难想但是会了第一步就会了的那种题。

第一步：
考虑如果我们确定了路径，对每个点应该在路径的什么位置打标记。
过一个点作一条斜率为 $-1$ 的直线，直线与路径的交点就是打标记的位置。
证明是这样：在这个位置上 $|X-x|$ 与 $|Y-y|$ 相等，从这个点沿着路径移动会使最大值不会变小。也可以这样理解：我们逐步扩大 $\max (|X-x|,|Y-y|)$ 直到与路径相交，那么相当于一个以 $(x,y)$ 为中心逐渐增大的的正方形，由于路径只能向上或向右，因此第一次与路径相交的点一定有正方形的左上角或右下角，与 $(x,y)$ 连线就是一条 $y=-x$ 的直线。

那么我们就知道了每个点被确定的顺序：过这个点作一条 斜率为 $-1$ 的直线，直线的 $b$ 越小就越早被确定。

考虑按照这个顺序 $dp$，设 $d{p}_{i,j}$ 表示确定了前 $i$ 个点，当前的横坐标为 $j$ 的最小花费。设 $b_i=x_i+y_i$。那么有转移：
$$d{p}_{i,j}\leftarrow \underset{b_{i-1}-b_i+j\le k\le j}{\min }d{p}_{i-1,k}+|j-x_i|$$

跟之前一样，先证明凸性，然后将转移分成两步。
第一步是右半部分向右平移，打标记即可。
第二步是加绝对值函数，维护最小值变化即可。

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

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 10;
typedef long long LL;
const LL INF = 1e10;
int n, odr[N];
LL x[N], y[N], tag;
bool cmp(int a, int b) {return x[a] + y[a] < x[b] + y[b];}
priority_queue< LL, vector< LL >, greater< LL > > qr;
priority_queue< LL, vector< LL >, less< LL > > ql;
void add(LL x, LL &ans) {LL l = ql.top(), r = qr.top() + tag;if(x >= l && x <= r) ql.push(x), qr.push(x - tag);else if(x < l) {ans += l - x; ql.push(x); ql.push(x); qr.push(ql.top() - tag); ql.pop();}else {ans += x - r;qr.push(x - tag); qr.push(x - tag);ql.push(r); qr.pop();}
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%lld%lld", &x[i], &y[i]);odr[i] = i;}sort(odr + 1, odr + n + 1, cmp);ql.push(0); qr.push(INF);LL ns = 0, ans = 0;for(int i = 1; i <= n;) {int j = i;while(j <= n && x[odr[j]] + y[odr[j]] == ns) j ++;for(int k = i; k < j; k ++ ) add(x[odr[k]], ans);if(j <= n) tag += x[odr[j]] + y[odr[j]] - ns;i = j; ns = x[odr[i]] + y[odr[i]];}cout << ans << endl;return 0;
}

P3642 [APIO2016] 烟火表演

给定一棵以 $1$ 为根 $n$ 个节点的树，每条边有一条边权 $c_i$。有 $m$ 个叶子。 将一条的边权从 $x$ 修改至 $y(y\ge 0)$ 需要的代价为 $|x-y|$。求将所有叶子到根节点的距离修改成相同的最小代价。

$1\le n+m\le 3\times 10^5$， $1\le c_i\le 10^9$。

分析：

神仙题。
首先还是先尝试列出一个 $dp$：设 $d{p}_{x,i}$ 表示修改 $x$ 子树中边权使得所有子树中的叶子到 $x$ 的距离都为 $i$ 的最小花费。
感性猜测 $d{p}_x$ 是关于 $i$ 的下凸函数。
先来考虑转移式，分成两步：

1. d p x , i = min ⁡ 0 ≤ j ≤ i { ∣ e x − j ∣ + d p x , i − j } dp_{x, i} = \min\limits_{0 \leq j \leq i}\{ |e_x - j| + dp_{x, i - j}\} dpx,i​=0≤j≤imin​{∣ex​−j∣+dpx,i−j​}
2. $d{p}_{f{a}_x,i}=\sum _{x\in so{n}_{f{a}_x}}d{p}_{x,i}$

其中 $e_x$ 表示 $x$ 与它的父亲之间的边权。
发现第二步就是若干下凸函数相加，是简单的。但是第一步的代价并不与 $i$ 相关，因此不能拆成 作前缀取 $\min$ 和 加一个绝对值函数。

那么从 $dp$ 的角度考虑是走不通的，考虑从函数图像上考虑：
设 $f(a)$ 表示 $d{p}_x$ 在经过第一步转移前凸包上 $x=a$ 的函数值。 $f^{\prime }(a)$ 表示第一步转移后得到的函数值。
设 $[L,R]$ 表示 $f(x)$ 的最小值段。这一段里的点斜率为 $0$。那么 $f(x)$ 的图像大概长这样：

分情况讨论：

• $L+e_x\le a\le R+e_x$ ， $f^{\prime }(a)=f(L)$。
  道理很简单，$L\le a-e_x\le R$，不用修改 $e_x$ 就可以落到最小值的区域。

• $L\le a<L+e_x$ ， $f^{\prime }(a)=f(L)+e_x-(a-L)$。
  原因是这样：相当于你最开始在 $(a-e_x,f(a-e_x))$ 这个点，你可以选择花费 $1$ 的代价从 $(x,f(x))$ 移动到 $(x+1,f(x+1))$，最后的花费就是移动花费加上当前的纵坐标，最多向右移动 $e_x$ 个单位长度。那么由于起点 $a-e_x<L$，因此斜率一定小于等于 $-1$，那么肯定尽量往右移动比较优，而移动到 $L$ 肯定就不用移了，因此代价为 $f(L)+e_x-(a-L)$。

• $a<L$，$f^{\prime }(a)=f(a)+e_x$。
  原因和上面类似，只不过这次移动不到 $L$ 了，因此移动最大距离到 $a$ 就是最优的。

• $R+e_x<a$，$f^{\prime }(a)=f(R)+(a-e_x)-R$。
  道理也是类似的。

那么我们通过 结合图像 得到了新函数的解析式。考虑凸包的变化情况：
先把四个式子列一遍：

• $L+e_x\le a\le R+e_x$， $f^{\prime }(a)=f(L)$。
• $L\le a<L+e_x$ ， $f^{\prime }(a)=f(L)+e_x-(a-L)$。
• $a<L$，$f^{\prime }(a)=f(a)+e_x$。
• $R+e_x<a$，$f^{\prime }(a)=f(R)+(a-e_x)-R$。

那么第一个式子相当于将凸包的极值段向右平移 $e_x$ 个单位长度。
第二个式子相当于将 $[L,L+e_x]$ 变成一段斜率为 $-1$ 的直线。
第三个式子相当于把 $a<L$ 的部分向上平移 $e_x$ 个单位。
第四个式子相当于把 $a>R+e_x$ 的部分变成一条斜率为 $1$ 的直线。

处理完四种操作后只需要将拐点合并即可。

先处理第四种：由于合并上来凸包的最大斜率都是 $1$，因此只需要删掉 $k-1$ 个拐点即可。$k$ 是儿子个数。
然后处理第二种：只需要将极值段的两个端点拿出来分别加上 $e_x$ 再插回去即可。
然后发现第二第三种操作已经做完了。

复杂度在于拐点的合并。我写的 启发式合并堆 是 $O(n{\log }^{2}n)$ 的，用 可并堆 是 $O(n\log n)$ 的(可惜我还不会 )。

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, m, head[N], len;
struct edge {int v, last;LL w;
}E[N * 2];
void add(int u, int v, LL w) {E[++ len] = (edge) {v, head[u], w};head[u] = len;
}
int son[N], sz[N], big[N];
priority_queue< LL > q[N];
LL node[N * 4];
void modify(int x, LL v) {for(int i = 1; i < son[x]; i ++ ) q[x].pop();LL a = q[x].top(); q[x].pop();LL b = q[x].top(); q[x].pop();q[x].push(a + v); q[x].push(b + v);
}
void Mg(int x, int y) {while(!q[y].empty()) q[x].push(q[y].top()), q[y].pop();
}
void dfs(int x, int fa) {sz[x] = 1;if(x > n) {q[x].push(0); q[x].push(0); q[x].push(0); return ;}for(int i = head[x]; i; i = E[i].last) {int v = E[i].v; LL w = E[i].w;if(v == fa) continue;dfs(v, x); sz[x] += sz[v];if(sz[v] > sz[big[x]]) big[x] = v;modify(v, w);}swap(q[x], q[big[x]]);for(int i = head[x]; i; i = E[i].last) {int v = E[i].v;if(v == fa || v == big[x]) continue;Mg(x, v); // x <- v}
}
int main() {scanf("%d%d", &n, &m);LL res = 0;for(int i = 2; i <= n + m; i ++ ) {int fa; LL l;scanf("%d%lld", &fa, &l); res += l;add(fa, i, l); add(i, fa, l);son[fa] ++;} dfs(1, 0);for(int i = 1; i <= son[1]; i ++ ) q[1].pop();int tot = 0; while(!q[1].empty()) {node[++ tot] = q[1].top(), q[1].pop();}LL k = 0;for(int i = tot; i > 1; i -- ) {if(node[i] == 0) k --;else k ++;res += k * (node[i - 1] - node[i]);}cout << res << endl;return 0;
}

[ABC275Ex] Monster

给定 $n$ 以及两个长度为 $n$ 的正整数序列 $A_i,B_i$，你可以执行以下操作任意次：

• 选定任意整数 $l,r$，满足 $1\le l\le r\le n$。
• 花费 max ⁡ i = l r { B i } \max\limits_{i = l}^{r}\{B_i\} i=lmaxr​{Bi​} 的代价，将 $A_l,A_{l+1},...,A_r$ 中每个都减去 $1$。

求出使得 $A_i$ 中元素全部 $\le 0$ 所需的最小代价。

$1\le n\le 10^5$， $1\le A_i,B_i\le 10^9$。

分析：
没看题解自己做出来的。
留作日后复习的思考题吧。

提示：笛卡尔树。