NOI2015 软件包管器

https://www.luogu.org/problem/P2146

题意

维护一棵树，每个节点都有一个为0或1的值，初始值全为0

需要支持

将一条链上的点都变成1，

将一棵子树中的点都变成0，

并统计每次操作改变了多少点的状态。

分析

每次修改链的时候，要记住，他们可能不在同一条重链上（其它题目里面的链修改也要注意），所以，我们需要跳...ctrl

线段树维护区间和，tag表示全改为0/1即可

（遇到错误不要慌！！！手模拟一遍样例说不定就找到错误了）

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN = 100000+99;

const int MAXM = MAXN<<1;

int n,m;

struct node{

	int deep, size, son, fa, tp, in, out;

}a[MAXN];

int _clock;

int head[MAXN], cnt;

struct seg{

	int y, next;

}e[MAXM];

void add_edge(int x, int y) {

	e[++cnt].y = y;

	e[cnt].next = head[x];

	head[x] = cnt;

}

void dfs1(int x, int fa) {

	a[x].fa = fa;

	a[x].deep = a[fa].deep + 1;

	a[x].size = 1;

	for(int i = head[x]; i; i = e[i].next)

		if(e[i].y != fa) {

			dfs1(e[i].y, x);

			a[x].size += a[e[i].y].size;

			a[x].son = a[a[x].son].size > a[e[i].y].size ? a[x].son : e[i].y ;

		}

}

void dfs2(int x, int tp) {

	a[x].tp = tp;

	a[x].in = ++_clock;

	if(a[x].son) dfs2(a[x].son , tp);

	for(int i = head[x]; i; i = e[i].next)

		if(e[i].y != a[x].fa && e[i].y != a[x].son) {

			dfs2(e[i].y , e[i].y);

		}

	a[x].out = _clock;

}

struct tree{

	int sum, lazyset;

	tree (int sum = 0, int lazyset = -1) : sum(sum), lazyset(lazyset) {}

}tr[MAXN<<2];

void pushup(int o) {tr[o].sum = tr[o<<1].sum + tr[o<<1|1].sum;}

void pushdown(int o, int l, int r) {

	if(tr[o].lazyset == -1) return ;

	tr[o<<1].lazyset = tr[o<<1|1].lazyset = tr[o].lazyset ;

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

	tr[o<<1].sum = tr[o].lazyset * (mid-l+1);

	tr[o<<1|1].sum = tr[o].lazyset * (r-mid);

	tr[o].lazyset = -1;

}

void optset(int o, int l, int r, int ql, int qr, int k) {

	if(ql <= l && r <= qr) {

		tr[o].sum = k*(r-l+1);

		tr[o].lazyset = k;

		return ;

	}

	pushdown(o, l, r);

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

	if(ql <= mid) optset(o<<1, l, mid, ql, qr, k);

	if(mid < qr) optset(o<<1|1, mid+1, r, ql, qr, k);

	pushup(o);

}

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

	if(ql <= l && r <= qr) return tr[o].sum;

	pushdown(o, l, r);

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

	if(ql <= mid) ans += query(o<<1, l, mid, ql, qr);

	if(mid < qr) ans += query(o<<1|1, mid+1, r, ql, qr);

	return ans;

}

int update_lian(int x) {

	int ans = 0;

	while(a[x].tp != 1) {

		ans += (a[x].in-a[a[x].tp].in+1) - query(1, 1, n, a[a[x].tp].in, a[x].in);

		optset(1, 1,n, a[a[x].tp].in, a[x].in, 1);//这题我没想边界咋找，于是就每一步都减一下

		x = a[a[x].tp].fa;

	}

	ans += (a[x].in-a[a[x].tp].in+1) - query(1, 1, n, a[a[x].tp].in, a[x].in);

	optset(1, 1, n, a[a[x].tp].in, a[x].in, 1);

	return ans;

}

int update_tree(int x) {

	int ans = query(1, 1, n, a[x].in, a[x].out);

	optset(1, 1, n, a[x].in, a[x].out , 0);

	return ans;

}

int main() {

	scanf("%d",&n);

	int x,y;

	for(x = 2; x <= n; x++) {

		scanf("%d",&y);

		y++;

		add_edge(x, y);

		add_edge(y, x);

	}

	dfs1(1, 0);

	dfs2(1, 1);

	scanf("%d",&m);

	string cmd;

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

		cin>>cmd;

		scanf("%d",&x);

		x++;

		if(cmd[0] == 'i') {

			printf("%d\n",update_lian(x));

		} else {

			printf("%d\n",update_tree(x));

		}

	}

}

巴特西

NOI2015 软件包管器

题意

分析

最新文章

热门文章