10
18
2015
2

【树链剖分+线段树】NOI2015 软件包管理器

4196: [Noi2015]软件包管理器

Time Limit: 10 Sec  Memory Limit: 512 MB

Description

 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,…,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,Am−1依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。
 

Input

输入文件的第1行包含1个正整数n,表示软件包的总数。软件包从0开始编号。

随后一行包含n−1个整数,相邻整数之间用单个空格隔开,分别表示1,2,3,…,n−2,n−1号软件包依赖的软件包的编号。
接下来一行包含1个正整数q,表示询问的总数。
之后q行,每行1个询问。询问分为两种:
install x:表示安装软件包x
uninstall x:表示卸载软件包x
你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)。
 

Output

输出文件包括q行。

输出文件的第i行输出1个整数,为第i步操作中改变安装状态的软件包数。
 

本子OJ传送门

2天学个树剖来水一水= =

人话:给定一颗树。install x:求x到根节点链上0的个数,并把链上所有点赋值为1。uninstall x:求x子树中1的个数,并把子树所有点赋值为0。

简直树剖模板题【听说我Day1 230了?】

树剖:把子树中最长的一条链作为重链,由子树内dfs序连续,用一些黑科技进行数据维护、询问。

复杂度:分块思想【听说是log n】主要取决于黑科技的复杂度= =

pos[u]为u在dfs序的编号

记top[u]为u所在重链顶端,对于install只要不断沿着链向上爬,询问+修改就行了。

记tail[u]为u所在子树dfs序最大的(使得[pos[u],tail[u]]代表u的子树),对于uninstall只要一次询问+修改就行了。

询问+修改这里用线段树维护,差点写爆炸= =

就这么水过去了?就这么水过去了= =

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<string>
#define maxn 100010
#define maxm 600000
#define INF 1000000000
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
using namespace std;
int FR[maxn],NT[maxn*2],TO[maxn*2],Si=0;//树相关 
int dep[maxn],F[maxn],S[maxn],ch[maxn];//大法师相关 
int top[maxn],pos[maxn],tail[maxn],vid=0;//树剖相关 
void AE(int u,int v)
{
	++Si;
	TO[Si]=v;
	NT[Si]=FR[u];
	FR[u]=Si;
}
struct ST
{
	int l[maxm],r[maxm],v[maxm],tag[maxm],n;//1:全改为1     2:全改为0 
	void update(int x)
	{
		v[x]=v[lc(x)]+v[rc(x)];
	}
	void ope(int x,int arg)
	{
		tag[x]=arg;
		if (arg==1) v[x]=r[x]-l[x]+1;
		if (arg==2) v[x]=0;
	}
	void pushdown(int x)
	{
		if (tag[x]) 
		{
			ope(lc(x),tag[x]);
			ope(rc(x),tag[x]);
			tag[x]=0;
		}
	}
	void build(int x,int L,int R)
	{
		l[x]=L,r[x]=R;
		v[x]=0;
		if (L==R) return;
		int mid=L+R>>1;
		build(lc(x),L,mid);
		build(rc(x),mid+1,R);
	}
	void Modify(int x,int L,int R,int arg)
	{
		pushdown(x);
		if (L<=l[x]&&r[x]<=R)
		{
			ope(x,arg);
			return;
		}
		if (R<l[x]||r[x]<L) return;
		Modify(lc(x),L,R,arg);
		Modify(rc(x),L,R,arg);
		update(x);
	}
	int Query(int x,int L,int R)
	{
		pushdown(x);
		if (L<=l[x]&&r[x]<=R) return v[x];
		if (R<l[x]||r[x]<L) return 0;
		return Query(lc(x),L,R)+Query(rc(x),L,R);
	}
}T;

void dfs(int u,int f,int de)
{
	dep[u]=de,F[u]=f,S[u]=1,ch[u]=100005;
	for (int i=FR[u];i+1;i=NT[i])
		if (TO[i]!=f)
		{
			dfs(TO[i],u,de+1);
			S[u]+=S[TO[i]];
			if (S[TO[i]]>S[ch[u]]) ch[u]=TO[i];
		}
}

void get_pos(int u,int rt)
{
	top[u]=rt,pos[u]=tail[u]=++vid;
	if (ch[u]==100005) return;//链尾 
	get_pos(ch[u],rt);
	tail[u]=max(tail[u],tail[ch[u]]);//少加这句,调了30min
	for (int i=FR[u];i+1;i=NT[i])
		if (TO[i]!=ch[u]&&TO[i]!=F[u])
		{ 
			get_pos(TO[i],TO[i]);
			tail[u]=max(tail[u],tail[TO[i]]);
		} 
} 
int Install(int u)//统计链上0的个数 
{
	int r=top[u],d=dep[u]+1,res=0;
	while (r)
	{
		res+=T.Query(1,pos[r],pos[u]);
		T.Modify(1,pos[r],pos[u],1);
		u=F[r],r=top[u];
	}
	res+=T.Query(1,pos[r],pos[u]);
	T.Modify(1,pos[r],pos[u],1);
	return d-res;	
}
int Uninstall(int u)//统计子树中1的个数 
{
	int r=tail[u],res=T.Query(1,pos[u],r);
	T.Modify(1,pos[u],r,2);
	return res;
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
	memset(FR,-1,sizeof (FR));
	int n,Q;
	n=read();
	for (int i=1;i<n;i++)
	{
		int v;
		v=read();
		AE(i,v);
		AE(v,i);
	}
	dfs(0,-1,0);
	get_pos(0,0);
	T.build(1,1,vid);
	T.n=vid;
	Q=read();
	for (int i=1;i<=Q;i++)
	{
		char _233[10];
		int u;
		scanf("%s%d",_233,&u);
		if (_233[0]=='i')
			printf("%d\n",Install(u));
		else
			printf("%d\n",Uninstall(u));
	}
	return 0;
}
接下来学些什么呢= =,老司机求带
Category: NOI | Tags: 树链剖分 线段树 | Read Count: 641
jcvb 说:
2015年10月23日 09:19

%%%树剖小能手

Best WiFi names 说:
2022年8月08日 18:48

Finding the best WiFi names for their new connections or routers is that they want some cool or funny names that make them feel nice and at the same time when your friends, family, or someone comes over to your place don’t you think a nice name would make the charm of the house as well. Best WiFi names Moreover, you can not just add cool names to your Network SSID but have some Puns or Jokes intended through the WiFi name that can bring a nice laugh out of anyone who comes across your connection in their WiFi settings finder. Also sometimes you want to hide WiFi SSID for security reasons.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com