题意

给定一棵 \(n\) 个点的带点权树，以 \(1\) 为根， \(m\) 次询问,每次询问给出两个值 \(p, k\) ，求以下值：

\(p\) 的子树中距离 \(p \le k\) 的所有点权最小值，询问强制在线。

\(n \le 10^5 , m \le 10^6, TL = 6s\)

题解

如果不强制在线，直接线段树合并就做完了。

强制在线，不难想到用一些可持久化的结构来维护这些东西。

其实可以类似线段树合并那样考虑，也就是说每次合并的时候我们依然使用儿子的信息。

只要在合并 \(x, y\) 共有部分的时候建出新节点，然后权值是 \(x, y\) 权值的较小值，其他的部分直接连向那些单独有的子树信息即可。

其实实现是这样的：

	int Merge(int x, int y) {

		if (!x || !y) return x | y;

		int o = Newnode();

		ls[o] = Merge(ls[x], ls[y]);

		rs[o] = Merge(rs[x], rs[y]);

		minv[o] = min(minv[x], minv[y]);

		return o;

	}

这样的话，既可以保留子树信息，又可以得到这个节点新的信息。

最后空间复杂度就是 \(O(n \log n)\) ，时间复杂度是 \(O((n + m) \log n)\) 的。

总结

强制在线问题，用可持久化数据结构去解决就行了，也就是把平常的数据结构记历史版本，并尽量用之前的信息。

代码

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << (x) << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

#define pb push_back

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}

template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x(0), sgn(1); char ch(getchar());

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;

    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

    return x * sgn;

}

void File() {

#ifdef zjp_shadow

	freopen ("F.in", "r", stdin);

	freopen ("F.out", "w", stdout);

#endif

}

const int N = 1e5 + 1e3, inf = 0x3f3f3f3f;

#define lson ls[o], l, mid

#define rson rs[o], mid + 1, r

template<int Maxn>

struct Chair_Man_Tree {

	int ls[Maxn], rs[Maxn], minv[Maxn], Size;

	Chair_Man_Tree() { minv[0] = inf; }

	inline int Newnode() {

		int o = ++ Size; minv[o] = inf; return o;

	}

	void Update(int &o, int l, int r, int up, int uv) {

		if (!o) o = Newnode();

		if (l == r) { chkmin(minv[o], uv); return ; }

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

		up <= mid ? Update(lson, up, uv) : Update(rson, up, uv);

		minv[o] = min(minv[ls[o]], minv[rs[o]]);

	}

	int Query(int o, int l, int r, int ql, int qr) {

		if (!o) return inf;

		if (ql <= l && r <= qr) return minv[o];

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

		if (qr <= mid) return Query(lson, ql, qr);

		if (ql > mid) return Query(rson, ql, qr);

		return min(Query(lson, ql, qr), Query(rson, ql, qr));

	}

	int Merge(int x, int y) {

		if (!x || !y) return x | y;

		int o = Newnode();

		ls[o] = Merge(ls[x], ls[y]);

		rs[o] = Merge(rs[x], rs[y]);

		minv[o] = min(minv[x], minv[y]);

		return o;

	}

};

vector<int> G[N]; int val[N], rt[N], dep[N];

int n, S;

Chair_Man_Tree<N * 80> T;

void Dfs(int u, int fa = 0) {

	dep[u] = dep[fa] + 1;

	for (int v : G[u]) if (v != fa)

		Dfs(v, u), rt[u] = T.Merge(rt[u], rt[v]);

	T.Update(rt[u], 1, n, dep[u], val[u]);

}

int main () {

	File();

	n = read(); S = read(); 

	For (i, 1, n)

		val[i] = read();

	For (i, 1, n - 1) {

		int u = read(), v = read();

		G[u].pb(v); G[v].pb(u);

	}

	Dfs(S);

	int q = read(), ans = 0;

	For (i, 1, q) {

		int x = (read() + ans) % n + 1, k = (read() + ans) % n;

		printf ("%d\n", ans = T.Query(rt[x], 1, n, dep[x], min(dep[x] + k, n)));

	}

	return 0;

}

巴特西

Educational Codeforces Round 33 (Rated for Div. 2) F. Subtree Minimum Query（主席树合并）

题意

题解

总结

代码

最新文章

热门文章