题目大意
有 (n) 个平行宇宙，由某些平行宇宙添加或删除一个点（三维坐标）得到，
现在有 (m) 组询问，形如对于某个平行宇宙，费用为从该平行宇宙内某个点出发
到达指定 (x) 坐标的任意位置的欧几里得距离，
并且这些点本身出发需要费用，如何让费用最小，
保证原点在所有平行宇宙中均存在
解题过程
首先 (x) 坐标指定那么其实 (y) 坐标和 (z) 坐标可以被忽略，
那么询问可以转化为形如找到一个存在的 (x) ，
使得 (y=(x-x_0)^2+d)最小，其中(d)表示从这个 (x) 出发本身所需费用
把这个平方拆开可以得到 (y=x^2-2xcdot x_0 + {x_0}^2+d)
将常数项放前面可以得到 ({x_0}^2=2x_0cdot x-x^2+y-d)
也就是各点坐标为((2x,-x^2+d))，用斜率为 (x_0) 的直线扫描使得截距最小，那么这也就是求一个下凸壳
然后考虑平行宇宙怎么做，它会形成一棵树，那么点的存在就会锁定在一些dfs序的连续区间中，
也就可以转化成线段树维护dfs序的区间，点按横坐标为第一关键字，纵坐标为第二关键字排序，
如果强制在线询问的话那么就二分答案需要多带一个(log)，
否则可以按照斜率排序那么直接删除队头即可，时间复杂度(O(mlog_2n))
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#define rr register
using namespace std;
const int N = 500011;
typedef long long lll;
struct Point {
lll x, y;
inline Point operator -(const Point &t)const {
return (Point) {
x - t.x, y - t.y
};
}
} a[N];
struct rec {
int x, z, rk;
} q[N];
struct node {
int y, next;
} e[N];
vector<int>L[N], R[N];
vector<Point>K[N << 2];
lll ans[N];
int n, m, Q, rk[N], head[N << 2], dfn[N], et, v[N], tot, Z[N], as[N];
inline lll input() {
rr lll ans = 0, f = 1;
rr char c = getchar();
while (!isdigit(c))
f = (c == '-') ? -f : f, c = getchar();
while (isdigit(c))
ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
return ans * f;
}
inline void print(lll ans) {
if (ans < 0)
putchar('-'), ans = -ans;
if (ans > 9)
print(ans / 10);
putchar(ans % 10 + 48);
}
inline lll dj(Point x, Point y) {//数量积
return x.x * y.x + x.y * y.y;
}
inline lll cj(Point x, Point y) {//向量积
return x.x * y.y - x.y * y.x;
}
inline void add(int x, int y) {
e[++et] = (node) {y, as[x]}, as[x] = et;
}
inline void update(int k, int l, int r, int x, int y, int z) {
if (l == x && r == y) {
while (K[k].size() > 1 && cj(a[z] - K[k][K[k].size() - 1], a[z] - K[k][K[k].size() - 2]) <= 0)
K[k].pop_back();//下凸壳，也就是向量积为顺时针时弹出队尾
K[k].push_back(a[z]);
return;
}
rr int mid = (l + r) >> 1;
if (y <= mid)
update(k << 1, l, mid, x, y, z);
else if (x > mid)
update(k << 1 | 1, mid + 1, r, x, y, z);
else
update(k << 1, l, mid, x, mid, z), update(k << 1 | 1, mid + 1, r, mid + 1, y, z);
}
inline lll kxb(lll k, Point x) {//实际答案
return k * x.x + x.y;
}
inline lll query(int k, int l, int r, int x, int z) {
rr int len = K[k].size();
rr lll ans = -2e18;
if (len) {
while (head[k] < len - 1 && kxb(z, K[k][head[k]]) <= kxb(z, K[k][head[k] + 1]))
++head[k];
ans = kxb(z, K[k][head[k]]);
}
if (l == r)
return ans;
rr int mid = (l + r) >> 1;
if (x <= mid)
return max(ans, query(k << 1, l, mid, x, z));
else
return max(ans, query(k << 1 | 1, mid + 1, r, x, z));
}
inline void dfs(int x) {
dfn[x] = ++tot;
if (Z[x] > 0)
L[Z[x]].push_back(tot);//插入操作的开头
if (Z[x] < 0)
R[-Z[x]].push_back(tot - 1);//删除操作的结尾
for (rr int i = as[x]; i; i = e[i].next)
dfs(e[i].y);
if (Z[x] > 0)
R[Z[x]].push_back(tot);//插入操作的结尾
if (Z[x] < 0)
L[-Z[x]].push_back(tot + 1);//删除操作的开头
}
bool cmp1(int x, int y) {//横坐标第一关键字
return a[x].x < a[y].x || (a[x].x == a[y].x && a[x].y < a[y].y);
}
bool cmp2(rec x, rec y) {//按斜率排序
return x.z < y.z;
}
signed main() {
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
n = input(), Q = input(),
L[1].push_back(1),
R[1].push_back(n), v[1] = 1;
a[m = 1] = (Point) {
0, -input()
};
//令第一个点为原点
for (rr int i = 2; i <= n; ++i) {
rr int opt = iut();
add(input() + 1, i);
rr int z = input() + 2;
if (!v[z])
v[z] = ++m;//重新编号
if (opt == 1)
Z[i] = -v[z];//删除操作
else {
rr lll d = iut();
input(), input();
a[Z[i] = v[z]] = (Point) {
2 * d, -d *d - input()
};//添加点
}
}
for (rr int i = 1; i <= m; ++i)
rk[i] = i;
dfs(1), sort(rk + 1, rk + 1 + m, cmp1);
for (rr int i = 1; i <= m; ++i) {
rr int len = L[rk[i]].size();
for (rr int j = 0; j < len; ++j) {
rr int Ll = L[rk[i]][j], Rr = R[rk[i]][j];
if (Ll <= Rr)
update(1, 1, n, Ll, Rr, rk[i]);
}
}
for (rr int i = 1; i <= Q; ++i)
q[i] = (rec) {
dfn[input() + 1], input(), i
};
sort(q + 1, q + 1 + Q, cmp2);
for (rr int i = 1; i <= Q; ++i)
ans[q[i].rk] = 1ll * q[i].z * q[i].z - query(1, 1, n, q[i].x, q[i].z);
for (rr int i = 1; i <= Q; ++i)
print(ans[i]), putchar(10);
return 0;
}