「SPOJ1487」Query on a tree III

传送门

把树的 \(\text{dfs}\) 序抠出来，子树的节点的编号位于一段连续区间，然后直接上建主席树区间第 \(k\) 大即可。

参考代码：

#include <algorithm>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 1e5 + 5;

int tot, head[_], nxt[_ << 1], ver[_ << 1];

inline void Add_edge(int u, int v)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int n, q, a[_], X[_], dfn[_], rev[_], siz[_], pos[_];

int tt, rt[_], lc[_ << 5], rc[_ << 5], cnt[_ << 5];

inline void build(int& p, int l = 1, int r = n) {

	p = ++tt;

	if (l == r) return ;

	int mid = (l + r) >> 1;

	build(lc[p], l, mid), build(rc[p], mid + 1, r);

}

inline void update(int& p, int q, int v, int l = 1, int r = n) {

	p = ++tt, lc[p] = lc[q], rc[p] = rc[q], cnt[p] = cnt[q] + 1;

	if (l == r) return ;

	int mid = (l + r) >> 1;

	if (v <= mid) update(lc[p], lc[q], v, l, mid);

	else update(rc[p], rc[q], v, mid + 1, r);

}

inline int query(int p, int q, int k, int l = 1, int r = n) {

	if (l == r) return l;

	int mid = (l + r) >> 1, num = cnt[lc[p]] - cnt[lc[q]];

	if (num >= k) return query(lc[p], lc[q], k, l, mid);

	else return query(rc[p], rc[q], k - num, mid + 1, r);

}

inline void dfs(int u, int f) {

	rev[dfn[u] = ++dfn[0]] = u, siz[u] = 1;

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue ;

		dfs(v, u), siz[u] += siz[v];

	}

}

int main() {

	read(n);

	for (rg int i = 1; i <= n; ++i) read(a[i]), X[i] = a[i];

	sort(X + 1, X + n + 1);

	for (rg int i = 1; i <= n; ++i)

		a[i] = lower_bound(X + 1, X + n + 1, a[i]) - X, pos[a[i]] = i;

	for (rg int u, v, i = 1; i < n; ++i)

		read(u), read(v), Add_edge(u, v), Add_edge(v, u);

	dfs(1, 0), build(rt[0]);

	for (rg int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], a[rev[i]]);

	read(q);

	for (rg int l, r, x, k; q--; ) {

		read(x), read(k), l = dfn[x], r = dfn[x] + siz[x] - 1;

		printf("%d\n", pos[query(rt[r], rt[l - 1], k)]);

	}

	return 0;

}

巴特西

「SPOJ1487」Query on a tree III

「SPOJ1487」Query on a tree III

最新文章

热门文章