[NOI2015]软件包管理器-树链剖分

时间：2023-03-10 01:35:34
[NOI2015]软件包管理器-树链剖分 
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+5;

int n,m;

int e,begin[maxn],next[maxn],to[maxn],val[maxn];

struct segment_tree{

	int l,r,sum,mark;

}tree[maxn<<2];

int son[maxn],id[maxn],father[maxn],cnt,deep[maxn],size[maxn],top[maxn];

inline void add(int x,int y){

	to[++e] = y;

	next[e] = begin[x];

	begin[x] = e;

}

inline void dfs1(int x,int fa,int dep){

	deep[x] = dep;

	father[x] = fa;

	size[x] = 1;

	int maxson = -1;

	for(int i = begin[x];i;i = next[i]){

		int y = to[i];

		if(y == fa)continue;

		dfs1(y,x,dep+1);

		size[x] += size[y];

		if(size[y] > maxson)son[x] = y,maxson = size[y];

	}

}

inline void dfs2(int x,int ntop){

	id[x] = ++cnt;

	top[x] = ntop;

	if(!son[x])return;

	dfs2(son[x],ntop);

	for(int i = begin[x];i;i = next[i]){

		int y = to[i];

		if(y == father[x] || y == son[x])continue;

		dfs2(y,y);

	}

}

inline void pushup(int root){

	tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;

}

inline void pushdown(int root){

	if (tree[root].mark){

		tree[root<<1].mark = tree[root].mark;

		tree[root<<1|1].mark = tree[root].mark;

		tree[root<<1].sum = (tree[root].mark-1)*(tree[root<<1].r-tree[root<<1].l+1);

		tree[root<<1|1].sum = (tree[root].mark-1)*(tree[root<<1|1].r-tree[root<<1|1].l+1);

		tree[root].mark = 0;

	}

}

inline void build(int l,int r,int root){

	tree[root].l = l;

	tree[root].r = r;

	if(l == r)return;

	int mid = l+r>>1;

	build(l,mid,root<<1);

	build(mid+1,r,root<<1|1);

	pushup(root);

}

inline void update(int l,int r,int ql,int qr,int root,int x){

	if(ql > r || qr < l)return;

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

		tree[root].mark = x+1;

		tree[root].sum = x*(r-l+1);

		return;

	}

	pushdown(root);

	int mid = l+r>>1;

	update(l,mid,ql,qr,root<<1,x);

	update(mid+1,r,ql,qr,root<<1|1,x);

	pushup(root);

}

inline int query(int l,int r,int ql,int qr,int root){

	if(ql > r || qr < l)return 0;

	if(ql <= l && qr >= r)return tree[root].sum;

	pushdown(root);

	int mid = l+r>>1;

	return query(l,mid,ql,qr,root<<1)+query(mid+1,r,ql,qr,root<<1|1);

}

inline int Query(int l,int r,int ql,int qr,int root){

	if(ql > r || qr < l)return 0;

	if(ql <= l && qr >= r)return (r-l+1)-tree[root].sum;

	pushdown(root);

	int mid = l+r>>1;

	return Query(l,mid,ql,qr,root<<1)+Query(mid+1,r,ql,qr,root<<1|1);

}

inline void update_range(int u,int v,long long x){

	while(top[u] != top[v]){

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

		update(1,cnt,id[top[u]],id[u],1,x);

		u = father[top[u]];

	}

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

	update(1,cnt,id[u],id[v],1,x);

}

inline int query_range(int u,int v){

	int ans = 0;

	while(top[u] != top[v]){

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

		ans += Query(1,cnt,id[top[u]],id[u],1);

		u = father[top[u]];

	}

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

	return ans+Query(1,cnt,id[u],id[v],1);

}

int main() {

	cin>>n;

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

		cin>>x;

		x++;

		add(x,i);

	}

	dfs1(1,0,1);

	dfs2(1,1);

	build(1,cnt,1);

	cin>>m;

	while(m--){

		string dispose;

		int x;

		cin>>dispose>>x;

		x++;

		if(dispose == "install"){

			cout<<query_range(1,x)<<endl;

			update_range(1,x,1);

		}

		else{

			cout<<query(1,cnt,id[x],id[x]+size[x]-1,1)<<endl;

			update(1,cnt,id[x],id[x]+size[x]-1,1,0);

		}

	}

	return 0;

}

　　树链剖分这东西我还是只会用一点点，所以讲不出来做法，有的题实在心态爆炸看别人代码会发现真的是细节决定成败，以后尽量可以把思路讲出来，现在的状况是：只可意会不可言传！！！~~~

相关文章