Luogu P2146 软件包管理器（树链剖分+线段树）

题意

给定$n$个软件包，每个软件包都有一个依赖软件包，安装一个软件包必须安装他的依赖软件包，卸载一个软件包必须先卸载所有依赖于它的软件包。给定$m$此操作，每次一个操作$install/unistall$表示安装或者卸载。

题解

可以通过简单画图看出，在这个树形结构的依赖层次图上，安装一个包相当于安装其到根节点路径上的所有包，删除一个包相当于删除其与其子树的包。用一个重链剖分+线段树处理一下就行了。

#include <cstdio>

#include <algorithm>

using std::swap;

typedef long long ll;

const int N = 1e5 + 10;

int n, Q, x, ans;

int fa[N], dep[N], siz[N], son[N];

int top[N], dfn[N], time;

int cnt, from[N], to[N], nxt[N];

int bui[N << 2], set[N << 2];

inline void addEdge(int u, int v) {

	to[++cnt] = v, nxt[cnt] = from[u], from[u] = cnt;

}

void dfs1(int u) {

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

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

		int v = to[i]; dfs1(v), siz[u] += siz[v];

		if(siz[v] > siz[son[u]]) son[u] = v;

	}

}

void dfs2(int u, int t) {

	dfn[u] = ++time, top[u] = t;

	if(!son[u]) return ; dfs2(son[u], t);

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

		int v = to[i]; if(v == son[u]) continue;

		dfs2(v, v);

	}

}

void modify(int sl, int sr, int k, int o = 1, int l = 1, int r = n) {

	int len = r - l + 1;

	if(l >= sl && r <= sr) {

		if(k == 1) ans += len - bui[o], bui[o] = len;

		else ans += bui[o], bui[o] = 0;

		set[o] = k;

		return ;

	}

	int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;

	if(set[o]) {

		if(set[o] == 1) bui[lc] = (len - (len >> 1)), bui[rc] = (len >> 1);

		else bui[lc] = bui[rc] = 0;

		set[lc] = set[rc] = set[o], set[o] = 0;

	}

	if(sl <= mid) modify(sl, sr, k, lc, l, mid);

	if(sr > mid) modify(sl, sr, k, rc, mid + 1, r);

	bui[o] = bui[lc] + bui[rc];

}

inline void ins(int x) {

	int fx = top[x];

	while (fx != 1) modify(dfn[fx], dfn[x], 1), x = fa[fx], fx = top[x];

	modify(1, dfn[x], 1);

}

int main () {

	scanf("%d", &n);

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

		scanf("%d", fa + i), ++fa[i];

		addEdge(fa[i], i);

	}

	dfs1(1), dfs2(1, 1);

	scanf("%d", &Q);

	char opt[12];

	while(Q--) {

		scanf("\n%s%d", opt, &x), ans = 0, ++x;

		if(opt[0] == 'i') ins(x);

		else modify(dfn[x], dfn[x] + siz[x] - 1, -1);

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

	}

	return 0;

}

巴特西

Luogu P2146 软件包管理器（树链剖分+线段树）

题意

题解

最新文章

热门文章