【NOI2015】软件包管理器 – 徐亦轲的博客

据说是个树链剖分裸题。。

嗯是个裸题。。

每个点再记个子树里面最后一条边在线段树里的位置。

完了。

不知道树链剖分的话：树链剖分就是用一些鬼畜的方法在树上套线段树。

给个学习链接：http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html

然后代码：

// <manager.cpp> - 01/01/16 11:47:34
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define m ((l+r)>>1)
#define lq x<<1,l,m
#define rq x<<1|1,m+1,r
#define Q 1,1,tot
const int MAXN=100001;
int siz[MAXN],dep[MAXN],top[MAXN],f[MAXN],son[MAXN],w[MAXN],en[MAXN];
int tot;
vector <int> b[MAXN];
struct st{
	int val,lazy;
}t[MAXN<<3];
void dfs1(int x){
	siz[x]=1;son[x]=0;
	for(int i=0;i<b[x].size();i++){
		int next=b[x][i];
		dep[next]=dep[x]+1;
		f[next]=x;
		dfs1(next);
		siz[x]+=siz[next];
		if(!son[x]||siz[son[x]]<siz[next])son[x]=next;
	}
}
void dfs2(int x,int y){
	w[x]=++tot;top[x]=y;
	if(son[x])dfs2(son[x],y);
	for(int i=0;i<b[x].size();i++){
		if(b[x][i]==son[x])continue;
		dfs2(b[x][i],b[x][i]);
	}
	en[x]=tot;
}
void build(int x,int l,int r){
	t[x].val=0;
	t[x].lazy=-1;
	if(l==r)return;
	build(lq);build(rq);
}
void down(int x,int l,int r){
	t[x<<1].lazy=t[x<<1|1].lazy=t[x].lazy;
	t[x].lazy=-1;
}
void up(int x,int l,int r){
	if(t[x].lazy!=-1)t[x].val=t[x].lazy*(r-l+1);
	else t[x].val=t[x<<1].val+t[x<<1|1].val;
}
int query(int x,int l,int r,int ll,int rr,int p){
	if(ll<=l&&r<=rr){
		if(p)return r-l+1-t[x].val;
		return t[x].val;
	}
	int k=0;
	if(t[x].lazy!=-1)down(x,l,r);
	up(lq),up(rq);
	if(ll<=m)k+=query(lq,ll,rr,p);
	if(rr>m)k+=query(rq,ll,rr,p);
	return k;
}
void change(int x,int l,int r,int ll,int rr,int p){
	if(ll<=l&&r<=rr){
		t[x].lazy=p;
		up(x,l,r);
		return;
	}
	if(t[x].lazy!=-1)down(x,l,r);
	if(ll<=m)change(lq,ll,rr,p);
	else up(lq);
	if(rr>m)change(rq,ll,rr,p);
	else up(rq);
	up(x,l,r);
}
int install(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])swap(x,y);
		ans+=query(Q,w[top[x]],w[x],1);
		change(Q,w[top[x]],w[x],1);
		x=f[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	ans+=query(Q,w[top[x]],w[x],1);
	change(Q,w[top[x]],w[x],1);
	return ans;
}
int uninstall(int x){
	int ans=query(Q,w[x],en[x],0);
	change(Q,w[x],en[x],0);
	return ans;
}
int main(){
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	int n=getint();
	for(int i=1;i<n;i++)b[getint()].push_back(i);
	dfs1(0);dfs2(0,0);build(1,1,tot);
	int q=getint();
	string ask;
	while(q--){
		cin>>ask;int x=getint();
		if(ask[0]=='i')printf("%d\n",install(0,x));
		else printf("%d\n",uninstall(x));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// <manager.cpp> - 01/01/16 11:47:34

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define m ((l+r)>>1)

#define lq x<<1,l,m

#define rq x<<1|1,m+1,r

#define Q 1,1,tot

const int MAXN=100001;

int siz[MAXN],dep[MAXN],top[MAXN],f[MAXN],son[MAXN],w[MAXN],en[MAXN];

int tot;

vector <int> b[MAXN];

struct st{

int val,lazy;

}t[MAXN<<3];

void dfs1(int x){

siz[x]=1;son[x]=0;

for(int i=0;i<b[x].size();i++){

int next=b[x][i];

dep[next]=dep[x]+1;

f[next]=x;

dfs1(next);

siz[x]+=siz[next];

if(!son[x]||siz[son[x]]<siz[next])son[x]=next;

}

void dfs2(int x,int y){

w[x]=++tot;top[x]=y;

if(son[x])dfs2(son[x],y);

for(int i=0;i<b[x].size();i++){

if(b[x][i]==son[x])continue;

dfs2(b[x][i],b[x][i]);

}

en[x]=tot;

}

void build(int x,int l,int r){

t[x].val=0;

t[x].lazy=-1;

if(l==r)return;

build(lq);build(rq);

}

void down(int x,int l,int r){

t[x<<1].lazy=t[x<<1|1].lazy=t[x].lazy;

t[x].lazy=-1;

}

void up(int x,int l,int r){

if(t[x].lazy!=-1)t[x].val=t[x].lazy*(r-l+1);

else t[x].val=t[x<<1].val+t[x<<1|1].val;

}

int query(int x,int l,int r,int ll,int rr,int p){

if(ll<=l&&r<=rr){

if(p)return r-l+1-t[x].val;

return t[x].val;

}

int k=0;

if(t[x].lazy!=-1)down(x,l,r);

up(lq),up(rq);

if(ll<=m)k+=query(lq,ll,rr,p);

if(rr>m)k+=query(rq,ll,rr,p);

return k;

}

void change(int x,int l,int r,int ll,int rr,int p){

if(ll<=l&&r<=rr){

t[x].lazy=p;

up(x,l,r);

return;

}

if(t[x].lazy!=-1)down(x,l,r);

if(ll<=m)change(lq,ll,rr,p);

else up(lq);

if(rr>m)change(rq,ll,rr,p);

else up(rq);

up(x,l,r);

}

int install(int x,int y){

int ans=0;

while(top[x]!=top[y]){

if(dep[x]<dep[y])swap(x,y);

ans+=query(Q,w[top[x]],w[x],1);

change(Q,w[top[x]],w[x],1);

x=f[top[x]];

}

if(dep[x]<dep[y])swap(x,y);

ans+=query(Q,w[top[x]],w[x],1);

change(Q,w[top[x]],w[x],1);

return ans;

}

int uninstall(int x){

int ans=query(Q,w[x],en[x],0);

change(Q,w[x],en[x],0);

return ans;

}

int main(){

freopen("manager.in","r",stdin);

freopen("manager.out","w",stdout);

int n=getint();

for(int i=1;i<n;i++)b[getint()].push_back(i);

dfs1(0);dfs2(0,0);build(1,1,tot);

int q=getint();

string ask;

while(q--){

cin>>ask;int x=getint();

if(ask[0]=='i')printf("%d\n",install(0,x));

else printf("%d\n",uninstall(x));

}

return 0;

}