Codeforces 490F Treeland Tour（离散化 + 线段树合并）

题目链接 Treeland Tour

题目就是让你求树上LIS

先离散化，然后再线段树上操作。一些细节需要注意一下。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 200010;

int root[N];

int ls[N * 40], rs[N * 40], lis[N * 40], lds[N * 40];

int ncnt, n, ans;

int ret = 0;

vector <int> v[N];

int val[N];

int sx[N];

int icnt = 0;

void merge(int &x, int y){

	if (!x || !y){

		x = x + y;

		return;

	}

	lis[x] = max(lis[x], lis[y]);

	lds[x] = max(lds[x], lds[y]);

	ret = max(ret, max(lis[ls[x]] + lds[rs[y]], lds[rs[x]] + lis[ls[y]]));

	merge(ls[x], ls[y]);

	merge(rs[x], rs[y]);

}

void modify(int &x, int l, int r, int t, int v, int *a){

	if (!x) x = ++ncnt;

	a[x] = max(a[x], v);

	if (l == r) return;

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

	if (t <= mid) modify(ls[x], l, mid, t, v, a);

	else modify(rs[x], mid + 1, r, t, v, a);

}

int query(int x, int l, int r, int ql, int qr, int *a){

	if (l > r) return 0;

	if (!x) return 0;

	if (ql <= l && r <= qr) return a[x];

	int ret = 0, mid = (l + r) >> 1;

	if (ql <= mid) ret = max(ret, query(ls[x], l, mid, ql, qr, a));

	if (qr >  mid) ret = max(ret, query(rs[x], mid + 1, r, ql, qr, a));

	return ret;

}

void dfs(int x, int fa){

	for (auto u : v[x]){

		if (u == fa) continue;

		dfs(u, x);

	}

	ret = 0;

	int nlis = 0, nlds = 0, ilis, ilds;

	for (auto u : v[x]){

		if (u == fa) continue;

		ilis = query(root[u], 1, icnt, 1, val[x] - 1, lis);

		ilds = query(root[u], 1, icnt, val[x] + 1, icnt, lds);

		merge(root[x], root[u]);

		ans = max(ans, ilis + nlds + 1);

		ans = max(ans, ilds + nlis + 1);

		nlis = max(nlis, ilis);

		nlds = max(nlds, ilds);

	}

	ans = max(ans, ret);

	modify(root[x], 1, icnt, val[x], nlis + 1, lis);

	modify(root[x], 1, icnt, val[x], nlds + 1, lds);

}

int main(){

	scanf("%d", &n);

	rep(i, 1, n){

		scanf("%d", val + i);

		sx[++icnt] = val[i];

	}

	sort(sx + 1, sx + icnt + 1);

	icnt = unique(sx + 1, sx + icnt + 1) - sx - 1;

	rep(i, 1, n) val[i] = lower_bound(sx + 1, sx + icnt + 1, val[i]) - sx;

	rep(i, 2, n){

		int x, y;

		scanf("%d%d", &x, &y);

		v[x].push_back(y);

		v[y].push_back(x);

	}

	dfs(1, 0);

	printf("%d\n", ans);

	return 0;

}