比赛链接：https://vjudge.net/contest/840008。
P3256 [JLOI2013] 赛车
每一辆车其实就相当于一个一次函数：\(v_i\cdot t+k_i\)。我们要做的就是维护全局的上凸包。
对每一个函数按斜率从小到大排序，对于当前元素 \(i\)，设 \(i\) 追上 \(j\) 的时间为 \(T_1\)，若：
- 当前栈的大小为 \(1\)：若 \(k_i>k_j\)，说明 \(i\) 一开始速度与所处位置都优于 \(j\)，那么 \(j\) 一定不能为答案做贡献，就推出栈
- 当前栈的大小大于 \(1\)：设栈倒数第二个元素为 \(p\)，设 \(j\) 追上 \(p\) 的时间为 \(T_2\)。若 \(T_2>T_1\)，说明 \(j\) 在追上别人前已经被别人追上了，那么 \(j\) 一定不能为答案做贡献，就推出栈
之后这样维护整个栈，最后的栈中元素就是答案。
注意 \(t=0\) 比赛还没开始，注意去重。
#include <bits/stdc++.h>
using namespace std;using ll = long long;const int N = 1e4 + 10;struct Car { ll k, v, id; } a[N];struct Line { ll k, v; int l, r; } line[N];int n, m, top, ans_cnt;
int st[N], ans[N];bool cmp_le(ll num1, ll den1, ll num2, ll den2) { return (__int128)num1 * den2 < (__int128)num2 * den1; }int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i].k;for (int i = 1; i <= n; i++) cin >> a[i].v;for (int i = 1; i <= n; i++) a[i].id = i;sort(a + 1, a + n + 1, [](const Car &x, const Car &y) {if (x.v != y.v) return x.v < y.v;return x.k < y.k;});for (int i = 1; i <= n; ) {int j = i;while (j <= n && a[j].v == a[i].v)j++;int k_start = j - 1;while (k_start - 1 >= i && a[k_start - 1].k == a[j - 1].k)k_start--;line[++m].v = a[i].v;line[m].k = a[j - 1].k;line[m].l = k_start;line[m].r = j - 1;i = j;}for (int i = 1; i <= m; i++) {while (top > 0) {Line cur = line[i];Line t1 = line[st[top]];ll num_new = t1.k - cur.k;ll den_new = cur.v - t1.v;if (top == 1) {if (num_new < 0) // t_new < 0，说明 t1 在 t=0 时起跑线就低于 curtop--;elsebreak;} else {Line t2 = line[st[top - 1]];ll num_old = t2.k - t1.k;ll den_old = t1.v - t2.v;if (cmp_le(num_new, den_new, num_old, den_old))top--;elsebreak;}}st[++top] = i;}for (int i = 1; i <= top; i++) {int idx = st[i];for (int j = line[idx].l; j <= line[idx].r; j++)ans[++ans_cnt] = a[j].id;}sort(ans + 1, ans + ans_cnt + 1);cout << ans_cnt << "\n";for (int i = 1; i <= ans_cnt; i++)cout << ans[i] << " ";cout << "\n";return 0;
}
P4069 [SDOI2016] 游戏
由于每一次操作新添加的值一定可以被处理为 \(k\times dep_i+b\)，故树链剖分 \(+\) 李超线段树。
#include <bits/stdc++.h>
#define maxn 100010
#define int long long
using namespace std;const int INF = 123456789123456789LL;int n, m, cnt;
vector<pair<int, int>> linker[maxn];// 树剖数组
int fa[maxn], dep[maxn], son[maxn], sz[maxn]; //父亲节点，节点深度，重儿子、子树大小
int top[maxn], id[maxn], rev[maxn]; //树链链头，dfs序节点编号，dfs序对应的原节点编号
int dis[maxn]; // 节点到根的距离// 李超树维护的线段
struct Line {int k, b;
} line[maxn * 4];
int mn[maxn * 4]; // 维护区间的最小值// 计算标号为 idx (线段树上位置) 在线段 l 上的值
int calc(int idx, Line l) {return l.k * dis[rev[idx]] + l.b;
}void dfs1(int x, int father) {fa[x] = father, dep[x] = dep[father] + 1, sz[x] = 1, son[x] = 0;for (auto edge : linker[x]) {int v = edge.first;if (v == father) continue; dis[v] = dis[x] + edge.second;dfs1(v, x);sz[x] += sz[v];if (sz[son[x]] < sz[v]) son[x] = v;}
}void dfs2(int x, int t) { top[x] = t, id[x] = ++cnt, rev[cnt] = x;if (!son[x]) return;dfs2(son[x], t);for (auto edge : linker[x]) {int v = edge.first;if (v == fa[x] || v == son[x]) continue;dfs2(v, v);}
}void build(int u, int l, int r) {line[u] = {0, INF}; // 初始时斜率为0，截距为INFmn[u] = INF;if (l == r) return;int mid = (l + r) >> 1;build(u * 2, l, mid);build(u * 2 + 1, mid + 1, r);
}// 核心：标记永久化的李超树下放与极值更新
void update_line(int u, int l, int r, Line newline) {int cl_new = calc(l, newline), cr_new = calc(r, newline);int cl_old = calc(l, line[u]), cr_old = calc(r, line[u]);// 如果新线段全面处于劣势，直接返回if (cl_new >= cl_old && cr_new >= cr_old) return;// 如果新线段全面处于优势，替换后不再下传if (cl_new <= cl_old && cr_new <= cr_old) {line[u] = newline;} else {int mid = (l + r) >> 1;int cmid_new = calc(mid, newline), cmid_old = calc(mid, line[u]);// 找出优势线段if (cmid_new < cmid_old) {swap(line[u], newline);swap(cl_new, cl_old);swap(cr_new, cr_old);}// 把劣势线段继续往下扔（扔向仍然有潜在可能发挥作用的一边）if (cl_new < cl_old) update_line(u * 2, l, mid, newline);else update_line(u * 2 + 1, mid + 1, r, newline);}// pushup，根据标记永久化，当前节点的极值由本节点最优线段的端点值以及子节点的极值共同决定mn[u] = min(calc(l, line[u]), calc(r, line[u]));if (l != r) mn[u] = min({mn[u], mn[u * 2], mn[u * 2 + 1]});
}void change(int u, int l, int r, int sl, int sr, Line newline) {if (sl <= l && r <= sr) {update_line(u, l, r, newline);return;}int mid = (l + r) >> 1;if (sl <= mid) change(u * 2, l, mid, sl, sr, newline);if (sr > mid) change(u * 2 + 1, mid + 1, r, sl, sr, newline);// 路径上涉及的节点同样需要更新 mnmn[u] = min(calc(l, line[u]), calc(r, line[u]));if (l != r) mn[u] = min({mn[u], mn[u * 2], mn[u * 2 + 1]});
}int query(int u, int l, int r, int sl, int sr) {if (sl <= l && r <= sr) return mn[u]; // 完全覆盖直接发挥标记永久化的优势返回子树极值int mid = (l + r) >> 1, res = INF;// 获取当前节点携带的优势线段，在目标区间 [sl, sr] 里的极值int L_sub = max(l, sl), R_sub = min(r, sr);if (L_sub <= R_sub) res = min(calc(L_sub, line[u]), calc(R_sub, line[u]));if (sl <= mid) res = min(res, query(u * 2, l, mid, sl, sr));if (sr > mid) res = min(res, query(u * 2 + 1, mid + 1, r, sl, sr));return res;
}int get_lca(int x, int y) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);x = fa[top[x]];}return dep[x] < dep[y] ? x : y;
}void update_path(int s, int t, int a, int b) {int w = get_lca(s, t);// 处理 s -> w 向上的一半int k1 = -a, b1 = a * dis[s] + b, u = s;while (top[u] != top[w]) {change(1, 1, n, id[top[u]], id[u], {k1, b1});u = fa[top[u]];}change(1, 1, n, id[w], id[u], {k1, b1});// 处理 w -> t 向下的一半 (注意此时不应重复覆盖 w)int k2 = a, b2 = a * (dis[s] - 2 * dis[w]) + b, v = t;while (top[v] != top[w]) {change(1, 1, n, id[top[v]], id[v], {k2, b2});v = fa[top[v]];}if (id[w] < id[v]) {change(1, 1, n, id[w] + 1, id[v], {k2, b2}); // w+1 规避了重复覆盖}
}int query_path(int x, int y) {int res = INF;while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);res = min(res, query(1, 1, n, id[top[x]], id[x]));x = fa[top[x]];}if (dep[x] < dep[y]) swap(x, y);res = min(res, query(1, 1, n, id[y], id[x]));return res;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1, u, v, w; i < n; i++) {cin >> u >> v >> w;linker[u].push_back({v, w});linker[v].push_back({u, w});}dis[1] = 0;dfs1(1, 0), dfs2(1, 1);build(1, 1, n);while(m--) {int opt;cin >> opt;if (opt == 1) {int s, t, a, b;cin >> s >> t >> a >> b;update_path(s, t, a, b);} else if (opt == 2) {int s, t;cin >> s >> t;cout << query_path(s, t) << "\n";}}return 0;
}
P5545 [JSOI2016] 炸弹攻击2
Gemini 发力了！
你可以想象极角就是点 \(P\) 与原点 \(O\) 形成的一条射线 \(OP\) 与 \(x\) 轴正半轴成的角。
我们考虑枚举 \(S\)，以 \(S_x\) 为原点，枚举 \(T_i,T_j\)，如果 \(T_i,T_j\) 形成的极角应当 \(\le 180^\circ\)。
为什么呢？因为如果这样那么我们选择的射线范围就在这个极角的包含范围，如果有 \(> 180^\circ\) 的极角，那么射线就会跑到后面去，不合逻辑。
问题来了？为什么不全部统计后整体答案取半呢？因为 \(\le 180^\circ\) 部分与 \(> 180^\circ\) 的贡献不一样呀（这部分理解了好久）！
对于 \(T\) 进行极角排序后按双指针维护答案就好了。
#include <bits/stdc++.h>
using namespace std;const int N = 810;using ll = long long;struct Point {ll x, y; int type; // 0 代表敌人，1 代表激光塔Point() {}Point(long long _x, long long _y, int _type) : x(_x), y(_y), type(_type) {}// 判断点所在的半平面（用以极角排序的辅助函数）int sgn() const {if (x != 0) return x > 0 ? 1 : 0;return y > 0 ? 1 : 0;}
};// 极角排序的比较函数
bool cmp(const Point& a, const Point& b) {if (a.sgn() != b.sgn()) {return a.sgn() < b.sgn(); // 不同的半平面直接按半平面排}// 相同的半平面，按叉积（逆时针）排return a.x * b.y < a.y * b.x;
}int D, S, T;
Point enemies[N];
Point satellites[N];
Point towers[N];// 存储平移后的所有点（包括敌人和激光塔）
Point pts[N * 4];
int s[N * 4]; // 敌人的数量前缀和
int f[N * 4]; // 激光塔的数量前缀和
ll g[N * 4]; // 激光塔位置的敌人前缀和之和int main() {// 优化输入输出ios::sync_with_stdio(0);cin.tie(0);cin >> D;for (int i = 1; i <= D; ++i) {cin >> enemies[i].x >> enemies[i].y;enemies[i].type = 0;}cin >> S;for (int i = 1; i <= S; ++i)cin >> satellites[i].x >> satellites[i].y;cin >> T;for (int i = 1; i <= T; ++i) {cin >> towers[i].x >> towers[i].y;towers[i].type = 1;}long long ans = 0;// 依次枚举每个发射源（卫星）for (int i = 1; i <= S; ++i) {int cnt = 0;// 平移坐标：以当前发射源 satellites[i] 为原点for (int j = 1; j <= D; ++j) pts[++cnt] = Point(enemies[j].x - satellites[i].x, enemies[j].y - satellites[i].y, 0);for (int j = 1; j <= T; ++j) pts[++cnt] = Point(towers[j].x - satellites[i].x, towers[j].y - satellites[i].y, 1);// 极角排序sort(pts + 1, pts + cnt + 1, cmp);// 复制一倍，处理循环（去环）for (int j = 1; j <= cnt; ++j)pts[j + cnt] = pts[j];// 维护前缀和for (int j = 1; j <= cnt * 2; ++j) {s[j] = s[j - 1];f[j] = f[j - 1];g[j] = g[j - 1];if (pts[j].type == 0) {s[j]++; // 统计敌人} else {f[j]++; // 统计激光塔g[j] += s[j]; // 统计激光塔位置的s[j]}}int k = 1;for (int j = 1; j <= cnt; ++j) {if (pts[j].type == 1) { // 寻找激光塔作为起点if (k < j) k = j;// 用叉积判断夹角是否在 180 度以内。若 pts[j] x pts[k+1] <= 0，代表夹角不超过 180 度while (k + 1 < j + cnt && pts[j].x * pts[k + 1].y <= pts[j].y * pts[k + 1].x)k++;// 累加当前激光塔 E[j] 对所有合格 E[r] (r ∈ [j+1, k]) 的贡献之和ans += g[k] - g[j] - 1LL * s[j] * (f[k] - f[j]);}}}cout << ans << "\n";return 0;
}