Statement
一棵树,每个节点上有一个集合,每个儿子集合由父亲集合增加一个点 \((x_i,c_i)\) 或删除一个点得到。根节点集合为 \(\{(0,0,0,c_0)\}\)
多次询问,每次问 \(u\) 点的集合内,\(\min\{(x_i-x)^2+c_i\}\)
Solution
首先你认真读完题发现原题中 \(y,z\) 都是没用的
然后离线 DFS 一遍,问题变成加点,删点,问 \(\min_{i}(x_i-x)^2+c_i\)
化一下式子,变成 \(\displaystyle x^2+\min_{i}\{-2x_i\cdot x+x_i^2+c_i\}\)
于是考虑李超树,需要支持加直线、删直线,发现删不了。。。
于是线段树分治,考虑 DFS 序,一遍 DFS 可以找出所有直线的出现位置,做完了。
撤销可以直接撤销,当然你写可持久化李超树也没人拦着。
另一种方式:\(Ans_i=(x_i-x)^2+c_i\),要求 \(Ans_i\) 最小
化成:\(x_i^2+c_i=2x\cdot x_i+Ans_i-x^2\)
令 \(k=2x,b=Ans_i-x^2\),这是一个 \(y_i=kx_i+b\),每个点为 \((x_i,x_i^2+c_i)\),用 \(k=2x\) 来切这些点,要 \(b\) 最小
考虑维护下凸包,我们需要维护加点、删点
这可以直接平衡树维护,单 log
但是如果你不想写平衡树,那可以加个线段树分治。
发现这里的线段树分治,各节点之间没有顺序而言,意思就是我们可以任意顺序遍历他
而凸壳的维护很有优化前途,我们令 \(x\) 递增就可以线性插入、令询问斜率单增可以线性处理询问;凸包的归并也是线性的
于是我们对每个插入和询问都排一遍序就能同样做到 \(O(n\log n)\) 维护了。
Code 1
李超树,直接撤销
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 20], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putchar(x) ((O - obuf < (1 << 20)) ? (*O++ = x) : (fwrite(obuf, O - obuf, 1, stdout), O = obuf, *O++ = x))
inline ll Read() {
ll x = 0;
int f = 1;
char ch = getchar();
for (; ch < 48 || ch > 57; ch = getchar()) if (ch == '-') f = 0;
for (; 48 <= ch && ch <= 57; ch = getchar()) x = (x << 3) + (x << 1) + ch - 48;
return f ? x : -x;
}
inline void Write(ll x) {
if (!x) {
putchar(48);
} else {
static int stk[50], tp;
tp = 0;
while (x) stk[++tp] = x % 10, x /= 10;
while (tp) putchar(stk[tp--] + 48);
}
putchar('\n');
}
const int N = 5e5 + 10, M = 2e7 + 10;
vector<pair<ll, int>> Quer[N];
vector<int> G[N];
ll ans[N], X[N];
int n, m, Xtot;
struct Planet {
ll x, c;
} a[N];
struct Set {
int op, id;
} b[N];
int Get(ll x) {
return lower_bound(X + 1, X + Xtot + 1, x) - X;
}
int tim, dfn[N], revdfn[N], sz[N];
vector<pair<int, int>> Add[N], Del[N];
void DFS1(int u) {
dfn[u] = ++tim, revdfn[tim] = u, sz[u] = 1;
for (int v : G[u]) {
DFS1(v), sz[u] += sz[v];
}
if (b[u].op) {
Add[b[u].id].push_back({dfn[u], dfn[u] + sz[u] - 1});
} else {
Del[b[u].id].push_back({dfn[u], dfn[u] + sz[u] - 1});
}
}
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
struct Line {
ll k, b;
} line[N];
int tag[N << 2];
pair<int, int> Modif[M];
int Tim;
ll Val(int id, int x) {
return (!id) ? (ll)1e18 : line[id].k * X[x] + line[id].b;
}
void Upd(int u, int l, int r, int id) {
if (!tag[u]) return Modif[++Tim] = {u, tag[u]}, tag[u] = id, void();
if (Val(id, mid) < Val(tag[u], mid)) Modif[++Tim] = {u, tag[u]}, swap(tag[u], id);
if (Val(id, l) < Val(tag[u], l)) Upd(lc, l, mid, id);
else if (Val(id, r) < Val(tag[u], r)) Upd(rc, mid + 1, r, id);
}
ll Qry(int u, int l, int r, int x) {
if (l == r) return Val(tag[u], x);
return min(Val(tag[u], x), (x <= mid) ? Qry(lc, l, mid, x) : Qry(rc, mid + 1, r, x));
}
vector<int> Segments[N << 2];
void Ins(int u, int l, int r, int x, int y, int v) {
if (y < l || r < x || x > y) return;
if (x <= l && r <= y) return Segments[u].push_back(v);
Ins(lc, l, mid, x, y, v), Ins(rc, mid + 1, r, x, y, v);
}
void Solve(int u, int l, int r) {
int OriginTim = Tim;
for (auto p : Segments[u]) {
Upd(1, 1, Xtot, p);
}
if (l == r) {
for (auto p : Quer[revdfn[l]])
ans[p.second] = p.first * p.first + Qry(1, 1, Xtot, Get(p.first));
} else {
Solve(lc, l, mid), Solve(rc, mid + 1, r);
}
reo(i, Tim, OriginTim + 1) {
tag[Modif[i].first] = Modif[i].second;
}
Tim = OriginTim;
}
#undef lc
#undef rc
#undef mid
int main() {
n = Read(), m = Read(), a[1].c = Read(), b[1].op = 1, b[1].id = 1;
rep(i, 2, n) {
int op = Read(), fr = Read() + 1, id = Read() + 1, x;
ll c;
G[fr].push_back(i);
if (op == 0) {
x = Read(), Read(), Read(), c = Read(), a[id] = {x, c}, b[i] = {1, id};
} else {
b[i] = {0, id};
}
}
rep(i, 1, m) {
int s = Read();
ll x0 = Read();
Quer[++s].push_back({x0, i});
X[++Xtot] = x0;
}
DFS1(1);
rep(i, 1, n) {
sort(Add[i].begin(), Add[i].end());
sort(Del[i].begin(), Del[i].end());
int pos = -1, R = Del[i].size();
for (auto p : Add[i]) {
int last = p.first;
while (pos < R - 1 && Del[i][pos + 1].second <= p.second) {
auto now = Del[i][++pos];
Ins(1, 1, n, last, now.first - 1, i);
last = now.second + 1;
}
Ins(1, 1, n, last, p.second, i);
}
}
rep(i, 1, n) line[i] = {-2ll * a[i].x, a[i].x * a[i].x + a[i].c};
sort(X + 1, X + Xtot + 1);
Xtot = unique(X + 1, X + Xtot + 1) - X - 1;
Solve(1, 1, n);
rep(i, 1, m) Write(ans[i]);
fwrite(obuf, O - obuf, 1, stdout);
return 0;
}
Code 2
李超树,可持久化
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 5e5 + 10, M = 2e7 + 10;
vector<pair<ll, int>> Quer[N];
vector<int> G[N];
ll ans[N], X[N];
int n, m, Xtot;
struct Planet {
ll x, c;
} a[N];
struct Set {
int op, id;
} b[N];
int Get(ll x) {
return lower_bound(X + 1, X + Xtot + 1, x) - X;
}
int tim, dfn[N], revdfn[N], sz[N];
vector<pair<int, int>> Add[N], Del[N];
void DFS1(int u) {
dfn[u] = ++tim, revdfn[tim] = u, sz[u] = 1;
for (int v : G[u]) {
DFS1(v), sz[u] += sz[v];
}
if (b[u].op) {
Add[b[u].id].push_back({dfn[u], dfn[u] + sz[u] - 1});
} else {
Del[b[u].id].push_back({dfn[u], dfn[u] + sz[u] - 1});
}
}
#define mid ((l + r) >> 1)
struct Line {
ll k, b;
} line[N];
struct Node {
int lc, rc, tag;
} f[M];
int tot, rt[N << 2], Tot[N << 2];
ll Val(int id, int x) {
return (!id) ? (ll)1e18 : line[id].k * X[x] + line[id].b;
}
void Build(int &u, int l, int r) {
f[u = ++tot].tag = 0;
if (l == r) return;
Build(f[u].lc, l, mid), Build(f[u].rc, mid + 1, r);
}
void Upd(int &u, int l, int r, int id, int lim) {
if (u <= lim) f[++tot] = f[u], u = tot;
if (!f[u].tag) return f[u].tag = id, void();
if (Val(id, mid) < Val(f[u].tag, mid)) swap(f[u].tag, id);
if (Val(id, l) < Val(f[u].tag, l)) Upd(f[u].lc, l, mid, id, lim);
else if (Val(id, r) < Val(f[u].tag, r)) Upd(f[u].rc, mid + 1, r, id, lim);
}
ll Qry(int u, int l, int r, int x) {
if (l == r) return Val(f[u].tag, x);
return min(Val(f[u].tag, x), (x <= mid) ? Qry(f[u].lc, l, mid, x) : Qry(f[u].rc, mid + 1, r, x));
}
#define lc (u << 1)
#define rc ((u << 1) | 1)
vector<int> Segments[N << 2];
void Ins(int u, int l, int r, int x, int y, int v) {
if (y < l || r < x || x > y) return;
if (x <= l && r <= y) return Segments[u].push_back(v);
Ins(lc, l, mid, x, y, v), Ins(rc, mid + 1, r, x, y, v);
}
void Solve(int u, int l, int r, int fa = 0) {
rt[u] = rt[fa];
for (auto p : Segments[u]) {
Upd(rt[u], 1, Xtot, p, Tot[fa]);
}
Tot[u] = tot;
if (l == r) {
for (auto p : Quer[revdfn[l]])
ans[p.second] = p.first * p.first + Qry(rt[u], 1, Xtot, Get(p.first));
} else {
Solve(lc, l, mid, u), Solve(rc, mid + 1, r, u);
}
tot = Tot[fa];
}
#undef lc
#undef rc
#undef mid
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> m >> a[1].c, b[1].op = 1, b[1].id = 1;
rep(i, 2, n) {
int op, fr, id, x, y, z;
ll c;
cin >> op >> fr >> id, ++fr, ++id, G[fr].push_back(i);
if (op == 0) {
cin >> x >> y >> z >> c, a[id] = {x, c}, b[i] = {1, id};
} else {
b[i] = {0, id};
}
}
rep(i, 1, m) {
int s;
ll x0;
cin >> s >> x0;
Quer[++s].push_back({x0, i});
X[++Xtot] = x0;
}
DFS1(1);
rep(i, 1, n) {
sort(Add[i].begin(), Add[i].end());
sort(Del[i].begin(), Del[i].end());
int pos = -1, R = Del[i].size();
for (auto p : Add[i]) {
int last = p.first;
while (pos < R - 1 && Del[i][pos + 1].second <= p.second) {
auto now = Del[i][++pos];
Ins(1, 1, n, last, now.first - 1, i);
last = now.second + 1;
}
Ins(1, 1, n, last, p.second, i);
}
}
rep(i, 1, n) line[i] = {-2ll * a[i].x, a[i].x * a[i].x + a[i].c};
sort(X + 1, X + Xtot + 1);
Xtot = unique(X + 1, X + Xtot + 1) - X - 1;
Build(rt[0], 1, Xtot), Tot[0] = tot;
Solve(1, 1, n);
rep(i, 1, m) cout << ans[i] << '\n';
return 0;
}
Code 3
凸包
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 20], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putchar(x) ((O - obuf < (1 << 20)) ? (*O++ = x) : (fwrite(obuf, O - obuf, 1, stdout), O = obuf, *O++ = x))
inline ll Read() {
ll x = 0;
int f = 1;
char ch = getchar();
for (; ch < 48 || ch > 57; ch = getchar()) if (ch == '-') f = 0;
for (; 48 <= ch && ch <= 57; ch = getchar()) x = (x << 3) + (x << 1) + ch - 48;
return f ? x : -x;
}
inline void Write(ll x) {
if (!x) {
putchar(48);
} else {
static int stk[50], tp;
tp = 0;
while (x) stk[++tp] = x % 10, x /= 10;
while (tp) putchar(stk[tp--] + 48);
}
putchar('\n');
}
const int N = 5e5 + 10;
struct Query {
int s, id;
ll x, k;
} Quer[N];
vector<int> G[N];
ll ans[N];
int n, m;
struct Point {
ll x, y;
} a[N];
struct Set {
int op, id;
} b[N];
int tim, dfn[N], revdfn[N], sz[N];
vector<pair<int, int>> Add[N], Del[N];
void DFS(int u) {
dfn[u] = ++tim, revdfn[tim] = u, sz[u] = 1;
for (int v : G[u]) {
DFS(v), sz[u] += sz[v];
}
if (b[u].op) {
Add[b[u].id].push_back({dfn[u], dfn[u] + sz[u] - 1});
} else {
Del[b[u].id].push_back({dfn[u], dfn[u] + sz[u] - 1});
}
}
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
struct Convex {
vector<int> vec;
int pos;
void Insert(int u) {
for (int p = (int)vec.size() - 1; p > 0 && (a[vec[p]].y - a[vec[p - 1]].y) * (a[u].x - a[vec[p]].x) >= (a[u].y - a[vec[p]].y) * (a[vec[p]].x - a[vec[p - 1]].x); --p, vec.pop_back());
vec.push_back(u);
}
ll Query(ll k) {
if (vec.empty()) return 1e18;
for (; pos < (int)vec.size() - 1 && a[vec[pos + 1]].y - a[vec[pos]].y < k * (a[vec[pos + 1]].x - a[vec[pos]].x); ++pos);
return a[vec[pos]].y - k * a[vec[pos]].x;
}
} Conv[N << 2];
void Ins(int u, int l, int r, int x, int y, int v) {
if (y < l || r < x || x > y) return;
if (x <= l && r <= y) return Conv[u].Insert(v);
Ins(lc, l, mid, x, y, v), Ins(rc, mid + 1, r, x, y, v);
}
ll Qry(int u, int l, int r, int x, ll k) {
if (l == r) return Conv[u].Query(k);
return min(Conv[u].Query(k), x <= mid ? Qry(lc, l, mid, x, k) : Qry(rc, mid + 1, r, x, k));
}
#undef lc
#undef rc
#undef mid
int main() {
n = Read(), m = Read(), a[1].y = Read(), b[1].op = 1, b[1].id = 1;
rep(i, 2, n) {
int op = Read(), fr = Read() + 1, id = Read() + 1;
ll x, c;
G[fr].push_back(i);
if (op == 0) {
x = Read(), Read(), Read(), c = Read(), a[id] = {x, x * x + c}, b[i] = {1, id};
} else {
b[i] = {0, id};
}
}
rep(i, 1, m) {
int s = Read() + 1;
ll x0 = Read();
Quer[i] = {s, i, x0, 2ll * x0};
}
DFS(1);
vector<int> id(n, 0);
rep(i, 1, n) id[i - 1] = i;
sort(id.begin(), id.end(), [&](const int &u, const int &v) {
return a[u].x < a[v].x;
});
for (auto i : id) {
sort(Add[i].begin(), Add[i].end());
sort(Del[i].begin(), Del[i].end());
int pos = -1, R = Del[i].size();
for (auto p : Add[i]) {
int last = p.first;
while (pos < R - 1 && Del[i][pos + 1].second <= p.second) {
auto now = Del[i][++pos];
Ins(1, 1, n, last, now.first - 1, i);
last = now.second + 1;
}
Ins(1, 1, n, last, p.second, i);
}
}
sort(Quer + 1, Quer + m + 1, [&](const Query& u, const Query& v) {
return u.k < v.k;
});
rep(i, 1, m) ans[Quer[i].id] = Qry(1, 1, n, dfn[Quer[i].s], Quer[i].k) + Quer[i].x * Quer[i].x;
rep(i, 1, m) Write(ans[i]);
fwrite(obuf, O - obuf, 1, stdout);
return 0;
}
标签:sz,dfn,int,题解,ll,P5416,vec,UOJ,id
From: https://www.cnblogs.com/laijinyi/p/18449773