首页 > 其他分享 >洛谷 P9058 [Ynoi2004] rpmtdq

洛谷 P9058 [Ynoi2004] rpmtdq

时间:2023-12-28 18:55:06浏览次数:41  
标签:rt P9058 洛谷 int rpmtdq stk maxn fst top

洛谷传送门

类比 P9062 [Ynoi2002] Adaptive Hsearch&Lsearch 处理区间最近点对的思路,尝试只保留可能有贡献的点对。

处理树上路径容易想到点分治。设点 \(u\) 到分治中心的距离为 \(a_u\)。我们有 \(\text{dis}(u, v) \le a_u + a_v\)。

考虑一个点对 \((u, v)\) 什么时候一定没贡献。这里默认 \(u, v\) 跨过分治中心,若不跨过并且在这一层舍弃了还可以在下一层重新被考虑。若存在 \(w \in [u + 1, v - 1]\) 使得 \(\text{dis}(u, w) \le a_u + a_v\) 且 \(\text{dis}(w, v) \le a_u + a_v\) 那么 \((u, v)\) 就没用,放缩一下有 \(a_w \le a_v\) 且 \(a_w \le a_u\)。所以一个点对 \((u, v)\) 要满足 \(\max(a_u, a_v) < \min\limits_{i = u + 1}^{v - 1} a_i\) 才可能有贡献。

分类讨论一下。如果 \(a_u \le a_v\),那么 \(u\) 必须是 \(v\) 之前第一个比 \(a_u\) 小的点,用单调栈求一下即可。如果 \(a_u \ge a_v\) 那么 \(v\) 必须是 \(u\) 之后第一个比 \(a_v\) 小的点,倒着再做一遍即可。

根据上面的求法我们可以得到有贡献点对数量是 \(O(n \log n)\) 的。

接下来就是套路的扫描线了。扫右端点 \(r\),每次把 \(v = r\) 的点对加入。那么一次询问 \(l\) 就是查询 \([l, n]\) 的后缀最小值。树状数组维护即可。

总时间复杂度是 \(O(n \log^2 n + q \log n)\)。

code
// Problem: P9058 [Ynoi2004] rpmtdq
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9058
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

namespace IO {
    char ibuf[1 << 20], *iS, *iT, obuf[1 << 20], *oS = obuf;
#define writesp(x) write(x), pc(' ')
#define writeln(x) write(x), pc('\n')
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
	template<typename T = int>
    inline T read() {
        char ch = gh();
        T x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void flush () {
    	fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
	}
    inline void pc (char ch) {
    	if (oS == obuf + (1 << 20)) flush(); 
    	*oS++ = ch;
	}
	template<typename _Tp>
    inline void write (_Tp x) {
    	static char stk[64], *tp = stk;
    	if (x < 0) x = ~(x - 1), pc('-');
		do *tp++ = x % 10, x /= 10;
		while (x);
		while (tp != stk) pc((*--tp) | 48);
    }
}

using IO::read;
using IO::write;
using IO::pc;
using IO::flush;

const int maxn = 200100;
const int logn = 20;
const int maxm = 1000100;

ll n, m, ans[maxm], stk[maxn], dep[maxn];
int st[logn][maxn], dfn[maxn], tim;
vector<pii> G[maxn], qq[maxn];
vector<int> vc[maxn];

ll f[maxn], sz[maxn], rt, tot;
pii a[maxn];
bool vis[maxn];

void dfs2(int u, int fa, int t) {
	f[u] = sz[u] = 1;
	for (pii p : G[u]) {
		ll v = p.fst;
		if (v == fa || vis[v]) {
			continue;
		}
		dfs2(v, u, t);
		sz[u] += sz[v];
		f[u] = max(f[u], sz[v]);
	}
	f[u] = max(f[u], t - sz[u]);
	if (!rt || f[u] < f[rt]) {
		rt = u;
	}
}

void dfs3(int u, int fa, ll t) {
	a[++tot] = mkp(u, t);
	for (pii p : G[u]) {
		ll v = p.fst, d = p.scd;
		if (v == fa || vis[v]) {
			continue;
		}
		dfs3(v, u, t + d);
	}
}

void dfs(int u) {
	vis[u] = 1;
	tot = 0;
	dfs3(u, -1, 0);
	sort(a + 1, a + tot + 1);
	int top = 0;
	for (int i = 1; i <= tot; ++i) {
		while (top && a[stk[top]].scd > a[i].scd) {
			--top;
		}
		if (top) {
			vc[a[i].fst].pb(a[stk[top]].fst);
		}
		stk[++top] = i;
	}
	top = 0;
	for (int i = tot; i; --i) {
		while (top && a[stk[top]].scd > a[i].scd) {
			--top;
		}
		if (top) {
			vc[a[stk[top]].fst].pb(a[i].fst);
		}
		stk[++top] = i;
	}
	for (pii p : G[u]) {
		ll v = p.fst;
		if (vis[v]) {
			continue;
		}
		rt = 0;
		dfs2(v, u, sz[v]);
		dfs2(rt, -1, sz[v]);
		dfs(rt);
	}
}

void dfs4(int u, int fa) {
	dfn[u] = ++tim;
	st[0][tim] = fa;
	for (pii p : G[u]) {
		ll v = p.fst, d = p.scd;
		if (v == fa) {
			continue;
		}
		dep[v] = dep[u] + d;
		dfs4(v, u);
	}
}

inline int get(int i, int j) {
	return dfn[i] < dfn[j] ? i : j;
}

inline int qlca(int x, int y) {
	x = dfn[x];
	y = dfn[y];
	if (x > y) {
		swap(x, y);
	}
	++x;
	int k = __lg(y - x + 1);
	return get(st[k][x], st[k][y - (1 << k) + 1]);
}

inline ll qdis(int x, int y) {
	return dep[x] + dep[y] - dep[qlca(x, y)] * 2;
}

namespace BIT {
	ll c[maxn];
	
	inline void init() {
		mems(c, 0x3f);
	}
	
	inline void update(ll x, ll d) {
		for (int i = x; i; i -= (i & (-i))) {
			c[i] = min(c[i], d);
		}
	}
	
	inline ll query(ll x) {
		ll res = 9e18;
		for (int i = x; i <= n; i += (i & (-i))) {
			res = min(res, c[i]);
		}
		return res;
	}
}

void solve() {
	n = read();
	for (int i = 1, u, v, d; i < n; ++i) {
		u = read();
		v = read();
		d = read();
		G[u].pb(v, d);
		G[v].pb(u, d);
	}
	m = read();
	for (int i = 1, l, r; i <= m; ++i) {
		l = read();
		r = read();
		if (l >= r) {
			ans[i] = -1;
			continue;
		}
		qq[r].pb(l, i);
	}
	dfs2(1, -1, n);
	dfs2(rt, -1, n);
	dfs(rt);
	dfs4(1, 0);
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
	BIT::init();
	for (int i = 1; i <= n; ++i) {
		for (int j : vc[i]) {
			BIT::update(j, qdis(i, j));
		}
		for (pii p : qq[i]) {
			ans[p.scd] = BIT::query(p.fst);
		}
	}
	for (int i = 1; i <= m; ++i) {
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	flush();
	return 0;
}

标签:rt,P9058,洛谷,int,rpmtdq,stk,maxn,fst,top
From: https://www.cnblogs.com/zltzlt-blog/p/17933354.html

相关文章

  • 洛谷B3611 【模板】传递闭包 floyd/bitset
    目录floydbitset优化题目链接:https://www.luogu.com.cn/problem/B3611参考题解:https://www.luogu.com.cn/blog/53022/solution-b3611floyd#include<bits/stdc++.h>usingnamespacestd;constintmaxn=101;intn,f[maxn][maxn];intmain(){scanf("%d"......
  • 洛谷B3647 【模板】Floyd 题解 floyd算法 求 多源多汇最短路
    题目链接:https://www.luogu.com.cn/problem/B3647floyd算法:https://oi-wiki.org/graph/shortest-path/#floyd-算法示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=101;intn,m,f[maxn][maxn];intmain(){scanf("%d%d",&n......
  • 【题解】洛谷P1496 火烧赤壁 (离散化)
    P1496火烧赤壁-洛谷|计算机科学教育新生态(luogu.com.cn)我们首先先看数据,n<=20000,数据不多,但是范围大(-10^9<=Ai,Bi<=10^9),这时,就可以用离散化了。但是在这里我们会遇到区间重合的问题(也可以使用区间合并),如下图本题的题意是让我们求出燃烧位置的长度之和。区间重合时只......
  • 【题解】洛谷P1068 [NOIP2009 普及组] 分数线划定 (map)
    ##题目描述世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的$150\%$划定,即如果计划录取$m$名志愿者,则面试分数线为排名第$m\times150\%$(向......
  • 洛谷 P1229
    题目链接有4种结构。对于只有一个儿子(度为1)的结点,其子节点在左/右不影响先序/后序的遍历顺序,总树数*2。即每多一个度为1的结点,二叉树数量翻倍。即当先根序列为\(.....XY.....,\)后根序列为\(.........YX...\)时翻倍。求出这种结构的个数即可。#include<bits/stdc++.h>usi......
  • 【洛谷 P1781】宇宙总统 题解(高精度+结构体排序)
    宇宙总统题目描述地球历公元6036年,全宇宙准备竞选一个最贤能的人当总统,共有个非凡拔尖的人竞选总统,现在票数已经统计完毕,请你算出谁能够当上总统。输入格式第一行为一个整数,代表竞选总统的人数。接下来有行,分别为第一个候选人到第个候选人的票数。输出格式共两行,第一行是......
  • 【洛谷 P1093】[NOIP2007 普及组] 奖学金 题解(结构体排序)
    [NOIP2007普及组]奖学金题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前名学生发奖学金。期末,每个学生都有门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规......
  • 洛谷 P1957
    题目链接:在每一行,因为不确定第一个输入数据的类型,所以要用字符串输入。值得注意的是,\(\sfsprintf\)的函数原型为intsprintf(char*buffer,constchar*format[,argument]…);,其第一个参数是char*类型,因此在使用\(\sfsprintf\)时一般使用字符串数组charstr[]而不用\(\s......
  • 【洛谷】P1678 烦恼的高考志愿 (二分)
    题目描述在这里:P1678这道题用二分的思路就很容易想出,先把学校分数排好序,根据不满意度的定义,我们只需要每次找到第一个大于学生成绩的学校分数,然后再和最后一个小于学生分数的院校分数分别与学生成绩做差再打绝对值进行比较,取最小的一个累加到ans里就好啦代码如下#include<iostr......
  • 【洛谷】P1024 [NOIP2001 提高组] 一元三次方程求解 (二分)
    题目描述见此:P1024如何求一个方程的根呢qwq首先,根是什么,函数y=f(x)有零点⇔方程f(x)=0有实数根⇔函数y=f(x)的图象与x轴有交点。回顾我们高一学过的一个定理:零点存在性定理:如果函数y=f(x)在区间[a,b]上的图象是连续不断的一条曲线,并且有f(a)·f(b)<0,那么,函数y=f(x)在区间(a,b)......