前置知识
线段树 建图（？）
前言
接触到线段树优化建图还是因为做 "[USACO11OPEN] Mowing the Lawn G" 不想写单调队列优化 DP 到处找其他做法翻到的（
学了过后感觉很神奇，就是能用到题目不多，没什么拿来练习的题目。
用途
用于解决对于 \(u\to v=[l,r]\texttt{ / }u=[l,r]\to v\texttt{ / } u = [l_1,r_1]\to v=[l_2,r_2]\) 连边的优化。
对于暴力时间复杂度和边数都是 \(n\texttt{ / }n\texttt{ / }n^2\) 级别的。
线段树优化复杂度和边数都将是 \(\log n\texttt{ / }\log n\texttt{ / }\log^2 n\) 级别。
方法
思想
这是一颗线段树：
对于每个节点通常用来记录其区间 \([l,r]\) 的信息。
那让其维护的信息为到其区间内 \([l,r]\) 所有点的连边，线段树优化建图大致思想就出来了。
举个例子，对于 \(u\to v=[1,6]\)，我们只需要对 \([1,4],[5,6]\) 两个部分类似于打 lazy 标记，等到后面走到这个点时继续往下走其对应儿子节点就行了。
实现
- 建树。
其实就是普通的线段树的建树啦。
只不过因为还要往儿子节点走，需要往儿子节点连一条单向边（因为这条边其实是不存在的，边权通常设为 \(0\)，但有时也会视情况而变）。vector <pair <int, long long> > l [N << 1]; struct seg_node { int l, r, ls, rs; } t [N << 1]; long long e [N]; void add (int u, int v) { /* ... */ return ; } int a [N];// a [i] 存储在树中第 i 个对应的编号 int cnt; void build (int k, int l, int r) { t [k] .l = l; t [k] .r = r; if (l == r) { a [l] = k; return ; } int mid = (l + r) >> 1; t [k] .ls = ++ cnt; build (t [k] .ls, l, mid); t [k] .rs = ++ cnt; build (t [k] .rs, mid + 1, r); add (k, t [k] .ls); add (k, t [k] .rs); // 向儿子连边 return ; } - 连边。
也就相当于普通线段树的区间操作。
即是在当前区间 \([l,r]\) 被需要连边的区间 \([x,y]\) 包含时直接对 \([l,r]\) 连边不继续往下走儿子节点。
易得区间个数是 \(\log n\) 级别的。/* 这里实现的是单点 -> 区间 区间 -> 单点同理 区间 -> 区间记录第一个区间 [x1,y1] 的小区间对第二个区间 [x2,y2] 的小区间直接连边即可 */ void update (int k, int l, int r, int u) { if (r < t [k] .l || t [k] .r < l) { return ; } if (l <= t [k] .l && t [k] .r <= r) { add (u, k);// 直接连边 return ; } update (t [k] .ls, l, r, u); update (t [k] .rs, l, r, u); return ; } - 其他操作。
现在就可以进行最短路，Tarjan 等操作啦。
例题
Luogu P2627 [USACO11OPEN] Mowing the Lawn G
https://www.luogu.com.cn/problem/P2627
发现不能超过连续 \(k\) 个，则对于选位置 \(i\) 在 \([i+1,i+k+1]\) 必有一个位置选不了，那 \(i\to j=[i+1,i+k+1]\) 都有一条边权为 \(e_j\) 的边。
同时对起点建一个超级源点 \(0\to [1,k+1]\)，对终点也建一个超级源点 \([n-k,n]\to n+1\)。
则最后跑最短路得出的答案 \(dis_{n+1}\) 就为不选的点的 \(e_i\) 和最小值，答案即为 \(\sum_{i=1}^n e_i-dis_{n+1}\)。
假设 \(n,k\) 同级，每个点边数都为 \(\log n\) 级别，总边数就为 \(n \log n\) 级别，跑 Dijkstra 时间复杂度为 \(O(n\log(n\log n))\approx O(n\log n)\)，\(\log\log n\) 完全可以当作小常数来看就去掉了。
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector <pair <int, long long> > l [N << 1];
struct seg_node {
int l, r, ls, rs;
} t [N << 1];
long long e [N];
void add (int u, int v) {
long long w = (t [v] .l == t [v] .r ? e [t [v] .l] : 0);// 如果是单个点记得边权为 e [t [v] .l]
l [u] .emplace_back (v, w);
return ;
}
int a [N];
int cnt;
void build (int k, int l, int r) {
t [k] .l = l;
t [k] .r = r;
if (l == r) {
a [l] = k;
return ;
}
int mid = (l + r) >> 1;
t [k] .ls = ++ cnt;
build (t [k] .ls, l, mid);
t [k] .rs = ++ cnt;
build (t [k] .rs, mid + 1, r);
add (k, t [k] .ls);
add (k, t [k] .rs);
return ;
}
void update (int k, int l, int r, int u) {
if (r < t [k] .l || t [k] .r < l) {
return ;
}
if (l <= t [k] .l && t [k] .r <= r) {
add (u, k);
return ;
}
update (t [k] .ls, l, r, u);
update (t [k] .rs, l, r, u);
return ;
}
long long dis [N << 1];
bool vis [N << 1];
int main () {
int n, k;
scanf ("%d %d", & n, & k);
long long tot = 0;
for (int i = 1; i <= n; ++ i) {
scanf ("%lld", & e [i]);
tot += e [i];
}
build (++ cnt, 1, n + 1);// 建树记得加上 n + 1 这个点
for (int i = 0; i <= n; ++ i) {
update (1, i + 1, min (i + k + 1, n + 1), a [i]);// 注意右边界不能超过 n + 1
}
memset (dis, 0x3f3f3f, sizeof dis);
dis [0] = 0;
priority_queue <pair <long long, int> > q;
q .emplace (0, 0);
while (! q .empty ()) {
pair <long long, int> top = q .top ();
q .pop ();
int u = top .second;
if (vis [u]) {
continue;
}
vis [u] = 1;
for (pair <int, long long> i : l [u]) {
int v = i .first;
long long w = i .second;
if (dis [u] + w < dis [v]) {
dis [v] = dis [u] + w;
q .emplace (- dis [v], v);
}
}
}// dijkstra
printf ("%lld", tot - dis [a [n + 1]]);
return 0;
}