首页 > 其他分享 >P5416 = UOJ 198 时空旅行 题解

P5416 = UOJ 198 时空旅行 题解

时间：2024-10-07 09:22:24浏览次数：8  
标签：sz dfn int 题解 ll P5416 vec UOJ id

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

相关文章

  • 火星商店问题 题解
    Solution线段树套trie，秒了！\(O(n\log^2n)\)Code#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=1e5+......
  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案；我们重点考虑的是偶回文串结论：对于偶回文串\(u\)，从其最长的长度小于等于他的一半的回文后缀，或其父亲转移过来，一定是最优的证明：设\(u\)的一个回文子串为\(v\)（不是父亲），你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点，因为此......
  • LOJ 6041 事情的相似度 题解
    Statement先把串reverse，多次给\(l,r\)，求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\)：莫队+线段树/树状数组/set，用SA做\(nm/\omega\)：bitset乱搞\(\log^2\)：SAM+LCT+BIT在parent树上，LCP等于LCA的......
  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • P4093 序列 题解
    Statement给出\(n\) 个数的序列\(\{a_i\}\)，接下来\(m\)秒中每一秒会有一个数发生变化，然后恢复。问最长的子序列长度，使得任意时刻这个子序列不下降。\(n\le10^5\)Solution设\(b_i\)为\(i\)最小能变成的数，\(c_i\)为\(i\)最大能变成的数\[f(i)=\max_{j<i\landc......
  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义：随机数据下：任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下：每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\)，一次询......
  • Codeforces Rund 977 div2 个人题解(A~E1)
    CodeforcesRund977div2个人题解(A,B,C1,C2,E1)Dashboard-CodeforcesRound977(Div.2,basedonCOMPFEST16-FinalRound)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#includ......
  • 【题解】C - STEP
    目录题目内容DescriptionInputOutput数据规模与约定做法一思路代码做法2思路代码题目内容原题：洛谷P6492Description给定一个长度为\(n\)的字符序列\(a\)，初始时序列中全部都是字符L。有\(q\)次修改，每次给定一个\(x\)，若\(a_x\)为L，则将\(a_x\)修改成R，否则将\(a_x\)......
  • 常见问题解决 --- maven手动安装依赖jar包报错
    报错内容：执行命令mvninstall:install-file-DgroupId=com.beidouapp-DartifactId=SSDK-Dversion=4.0.2.0 -Dfile=C:\1\SSDK-Release-4.0.2.0.jar-Dpackaging=jar报错Unknownlifecyclephase“.ggstar“.Youmustspecifyavalidlifecyclephaseoragoal原因：在pow......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99