P5311 [Ynoi2011]成都七中

Ynoi2011某道题

"和我一起去qbxt听课的有一位ljh，他初二拿了普及组省第一，初三考提高组差点拿了一等奖，我一直以他为竞争对手，每次考试的时候都在和他比划比划成绩，但基本上都是我输。"

我是谁?你不会真当是博主了吧?

给你一棵 $n$ 个节点的树，每个节点有一种颜色，有 $m$ 次查询操作。

查询操作给定参数 $l \ r\ x$ ，需输出：

将树中编号在 $[l,r]$ 内的所有节点保留， $x$ 所在联通块中颜色种类数。

每次查询操作独立。

总的来说分两步,这个题就难在第一步上:

"我们考虑把它变成一个点子树内的询问"....这个谁想得到啊??之前做连通块计数那题只不是是启发式合并而已/QAQ

是的,就是变成一个子树内询问,然后对于每个点全部离线处理

然而想想都知道这个要用点分治来分子树,因为

支持暴力查找有多少根包含他(log大小)
保证每个询问都有合法包含
现成算法提供现成划分套路(

然后我们来用点分树,把 $[l,r]$ 都包含在一个点分支中心子树里面,然后这个询问就挂在这上面了

问题变成从根节点出发只走子树内编号范围在[l,r]的点可以到达的颜色总数?

第二歩,离线处理每个点的询问,考虑记录每个点到根经过最大的编号和最小的编号

那么只要经过最大编号比询问最大小,最小编号比询问最小大的点就能算作答案了

那这就是二维偏序了....按照最大排序,最小用树状数组

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5 + 7;

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		register char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;

int n, m, xi, yi, zi, root;
int col[MAXN], ans[MAXN], cx[MAXN],
	nxt[MAXN], to[MAXN], home[MAXN], ccnt
	, siz[MAXN], used[MAXN],  tot, dp[MAXN];

struct node {
	int l, r, id;
	node(): l(0), r(0), id(0) {};
	node(int L, int R, int ID): l(L), r(R), id(ID) {};
	bool operator<(const node &d)const {
		return l == d.l ? id > d.id : l > d.l;
	}

};
vector<node> v[MAXN], q[MAXN];

inline void ct(int x, int y) {
	++ccnt;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline void dfs1(int u, int fa) {
	dp[u] = siz[u] = 1;
	//printf("%d %d??\n", u, fa);
	for(int v, i = home[u]; i; i = nxt[i]) {
		v = to[i];
		//printf("%d %d!\n", u, v);
		if(v != fa && !used[v]) {
			dfs1(v, u);
			siz[u] += siz[v];
			dp[u] = max(dp[u], siz[v]);
		}
	}
	dp[u] = max(dp[u], tot - siz[u]);
	if(dp[u] < dp[root])root = u;
}

inline void dfs2(int u, int fa, int mx, int mn) {
	siz[u] = 1;

	v[u].push_back((node) {
		mn, mx, root
	});//查询答案要用,每个点归到各个分治中心
	q[root].push_back((node) {
		mn, mx, col[u]
	});//二维数点要用,每个分治中心管好子树内的点
	for(int v, i = home[u]; i; i = nxt[i]) {
		if((v = to[i]) != fa && !used[v]) {
			dfs2(v, u, max(mx, v), min(v, mn));
			siz[u] += siz[v];
		}
	}
}

inline void vp(int u) {
	tot = siz[u];
	dp[0] = 0x3f3f3f3f;
	root = 0;
	dfs1(u, 0);
	//printf("%d?\n", root);
	used[root] = 1;
	dfs2(u = root, 0, root, root);
	for(int v, i = home[u]; i; i = nxt[i]) {
		if(!used[(v = to[i])])vp(v);
	}
}
//点分治部分,写的很垃圾
int tree[MAXN << 1];
#define lowbit(x) (x&(-x))
inline void update(int pos, int v) {
	for(; pos <= n; pos += lowbit(pos))tree[pos] += v;
}

inline ll query(int pos) {
	ll ret = 0;
	for(; pos; pos -= lowbit(pos))ret += tree[pos];
	return ret;
}

int main() {
	//freopen("test.in", "r", stdin);
	n = read();
	m = read();
	for(int i = 1; i <= n; ++i)col[i] = read();
	for(int i = 1; i < n; ++i)xi = read(), yi = read(), ct(xi, yi), ct(yi, xi); //printf("%d %d?\n", xi, yi);
	siz[1] = n;
	//system("pause");
	vp(1);
	for(int i = 1; i <= m; ++i) {
		xi = read();
		yi = read();
		zi = read();
		for(vector<node>::iterator id = v[zi].begin(); id != v[zi].end(); ++id) {
			node j = *id;
			//你考虑每个vector里面存的是一个编号连续的点分树根
			//那么我能只要第一个找到的就是最优包含了x在查询的所有的
			if(j.l >= xi && j.r <= yi) {
				q[j.id].push_back((node) {
					xi, yi, -i//为什么-i因为他是询问
				});
				break;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		sort(q[i].begin(), q[i].end());
		//考虑每个点做根
		//排序是按照最大标号来,小的放前面,消掉第一维
		for(vector<node>::iterator id = q[i].begin(); id != q[i].end(); ++id) {
			node j = *id;
			//呵呵
			if(j.id < 0)ans[-j.id] = query(j.r);
			//树状数组消去第二维
			else {
				if(cx[j.id] > j.r)update(cx[j.id], -1), cx[j.id] = 0;
				//清掉他,他已经不够优秀
				if(!cx[j.id])update(j.r, 1), cx[j.id] = j.r;
				//更优秀的放进去
			}
		}
		for(vector<node>::iterator id = q[i].begin(); id != q[i].end(); ++id) {
			node j = *id;
			if(j.id > 0 && cx[j.id] == j.r)update(j.r, -1), cx[j.id] = 0;
		}
		//清空
	}
	for(int i = 1; i <= m; ++i)printf("%d\n", ans[i]);
	return 0;
}

夏晓光(loveJY)的博客

P1232 [NOI2013]树的计数