【BZOJ 4539】【HNOI 2016】树

http://www.lydsy.com/JudgeOnline/problem.php?id=4539

今天测试唯一会做的一道题。

按题目要求，如果暴力的把模板树往大树上仍，最后得到的大树是$O(n^2)$级别的，不能存储，更不能做了。

把模板树往大树上扔的过程我想象成了两个大节点进行连边，每个大节点代表模板树本身或一部分。

这相当于把初始的大树(此时和模板树相同)缩成一个大节点，每次把模板树的一部分缩成一个大节点往大节点构成的大树上连，最后连好的大节点构成的模板树是$O(n)$级别的。

每个节点里都套着一棵树，像树套树的模型。

这样在求距离和LCA的时候就可以先找到节点在哪个大节点里，求出在大节点内的一部分距离后，再在大节点构成的大树上倍增到LCA，统计距离。在LCA(大节点)中套着的树中继续倍增求LCA，统计距离。

每个大节点要维护的信息比较多；因为要按编号顺序从小到大加，所以还要在模板树的dfs序上用主席树查询第k大；倍增时还要注意特判几种特殊情况。在这里不再一一赘述。

测试时只有60分，后来拿到数据亲测一遍后发现到后期大树的节点到达$O(n^2)$级别，此时节点编号用int已经存不下了，所以存节点编号需要用long long。看来我还是too naive!!!

时间复杂度$O(n\log n)$

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 100003;

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

ll inll() {

	ll k = 0; int fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

int n, m, q;

namespace Small {

	struct node {

		int nxt, to;

	} E[N << 1];

	int cnt = 0, point[N], f[N][18], deep[N], L[N], R[N], a[N];

	bool vis[N];

	void ins(int u, int v) {

		E[++cnt].nxt = point[u]; E[cnt].to = v; point[u] = cnt;

	}

	void dfs(int x) {

		vis[x] = true; L[x] = ++cnt; a[cnt] = x;

		for(int i = point[x]; i; i = E[i].nxt) if (!vis[E[i].to]) {

			deep[E[i].to] = deep[x] + 1;

			f[E[i].to][0] = x;

			dfs(E[i].to);

		}

		R[x] = cnt;

	}

	struct node2 {

		int l, r, s;

	} T[N * 20];

	int root[N], tot = 0;

	void update(int &pos, int l, int r, int key) {

		T[++tot] = T[pos]; pos = tot; ++T[pos].s;

		if (l == r) return;

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

		if (key <= mid) update(T[pos].l, l, mid, key);

		else update(T[pos].r, mid + 1, r, key);

	}

	void BuildPT() {

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

			root[i] = root[i - 1];

			update(root[i], 1, n, a[i]);

		}

	}

	void work() {

		int u, v;

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

			u = in(); v = in();

			ins(u, v); ins(v, u);

		}

		cnt = 0; memset(vis, 0, sizeof(vis));

		deep[1] = 0; dfs(1);

		for(int j = 1; j < 18; ++j)

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

				f[i][j] = f[f[i][j - 1]][j - 1];

			}

		BuildPT();

	}

	int Sum(int x) {return R[x] - L[x] + 1;}

	int kth(int left, int right, int l, int r, int key) {

		if (l == r) return l;

		int mid = (l + r) >> 1, sum = T[T[right].l].s - T[T[left].l].s;

		if (sum >= key) return kth(T[left].l, T[right].l, l, mid, key);

		else return kth(T[left].r, T[right].r, mid + 1, r, key - sum);

	}

	int Query(int rt, int k) {

		int l = L[rt], r = R[rt];

		return kth(root[l - 1], root[r], 1, n, k);

	}

	int todeep(int a, int b) {return deep[a] - deep[b];}

	int LCA(int u, int v) {

		if (deep[u] < deep[v]) swap(u, v);

		int d = deep[u] - deep[v];

		for(int i = 17; i >= 0; --i)

			if ((1 << i) & d)

				u = f[u][i];

		if (u == v) return d;

		for(int i = 17; i >= 0; --i)

			if (f[u][i] != f[v][i]) {

				u = f[u][i]; v = f[v][i];

				d += (1 << (i + 1));

			}

		return d + 2;

	}

}

namespace Big {

	ll c[N][18];

	int f[N][18], deep[N];

	int tablenum = 0, table_to[N], table_rt[N];

	ll table_l[N], table_r[N], up;

	int pos(ll x) {

		int mid, left = 1, right = tablenum;

		while (left < right) {

			mid = (left + right) >> 1;

			if (x < table_l[mid]) right = mid - 1;

			else if (x > table_r[mid]) left = mid + 1;

			else return mid;

		}

		return left;

	}

	void work() {

		int a; ll b;

		up = n;

		tablenum = 1; table_l[1] = 1; table_r[1] = n; table_rt[1] = 1;

		for(int i = 1; i <= m; ++i) {

			a = in(); b = inll();

			int P = pos(b);

			table_rt[++tablenum] = a;

			table_l[tablenum] = up + 1;

			up += Small::Sum(a);

			table_r[tablenum] = up;

			f[tablenum][0] = P;

			deep[tablenum] = deep[P] + 1;

			table_to[tablenum] = Small::Query(table_rt[P], b - table_l[P] + 1);

			c[tablenum][0] = Small::todeep(table_to[tablenum], table_rt[P]) + 1;

		}

		for(int j = 1; j < 18; ++j)

			for(int i = 1; i <= tablenum; ++i) {

				f[i][j] = f[f[i][j - 1]][j - 1];

				c[i][j] = c[i][j - 1] + c[f[i][j - 1]][j - 1];

			}

		int changeu, changev, posu, vnum, posv, u, v;

		ll U, V, ret;

		for(int i = 1; i <= q; ++i) {

			U = inll(); V = inll(); ret = 0;

			posu = pos(U); posv = pos(V);

			if (deep[posu] < deep[posv]) {

				swap(posu, posv); swap(U, V);

			}

			changeu = Small::Query(table_rt[posu], U - table_l[posu] + 1);

			changev = Small::Query(table_rt[posv], V - table_l[posv] + 1);

			if (posu == posv) {

				printf("%d\n", Small::LCA(changeu, changev));

				continue;

			}

			u = posu; v = posv;

			for(int i = 17; i >= 0; --i)

				if (deep[f[u][i]] > deep[v]) {

					ret += c[u][i];

					u = f[u][i];

				}

			if (f[u][0] == v) {

				ret += 1;

				u = table_to[u];

				v = changev;

				ret += Small::LCA(u, v);

				ret += Small::todeep(changeu, table_rt[posu]);

			} else {

				if (deep[u] > deep[v]) {

					ret += c[u][0];

					u = f[u][0];

				}

				for(int i = 17; i >= 0; --i)

					if (f[u][i] != f[v][i]) {

						ret += (c[u][i] + c[v][i]);

						u = f[u][i];

						v = f[v][i];

					}

				ret += 2;

				ret += Small::LCA(table_to[u], table_to[v]);

				ret += Small::todeep(changeu, table_rt[posu]) + Small::todeep(changev, table_rt[posv]);

			}

			printf("%lld\n", ret);

		}

	}

}

int main() {

	n = in(); m = in(); q = in();

	Small::work();

	Big::work();

	return 0;

}

遇到看到不可做的题一定要认真地思考，看透每个操作的本质，找到操作中重复的东西并利用它化简空间复杂度和时间复杂度。一定要想好了在写，考虑到方方面面，任何细节都很关键。就像这次测试因为节点编号没有用long long存储导致$O(n\log n)$复杂度的得分被卡成$O(n^2)$复杂度的得分。

巴特西

【BZOJ 4539】【HNOI 2016】树

最新文章

热门文章