【BZOJ 1146】 [CTSC2008]网络管理Network

浏览数：57 / 时间：2015年06月09日

1146: [CTSC2008]网络管理Network

Time Limit: 50 Sec Memory Limit: 162 MB
Submit: 1938 Solved: 577
[Submit][Status]

Description

M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。【任务】你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。并依次处理这Q条询问信息，它们可能是： 1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。 2. 查询某两个路由器a和b之间的路径上延迟第k大的路由器的延迟时间。

Input

第一行为两个整数N和Q，分别表示路由器总数和询问的总数。第二行有N个整数，第i个数表示编号为i的路由器初始的数据延迟时间Ti。紧接着N-1行，每行包含两个整数x和y。表示有一条光缆连接路由器x和路由器y。紧接着是Q行，每行三个整数k、a、b。如果k=0，则表示路由器a的状态发生了变化，它的数据交换延迟时间由Ta变为b。如果k>0，则表示询问a到b的路径上所经过的所有路由器（包括a和b）中延迟第k大的路由器的延迟时间。注意a可以等于b，此时路径上只有一个路由器。

Output

对于每一个第二种询问（k>0），输出一行。包含一个整数为相应的延迟时间。如果路径上的路由器不足k个，则输出信息“invalid request!”（全部小写不包含引号，两个单词之间有一个空格）。

Sample Input

5 5
5 1 2 3 4
3 1
2 1
4 3
5 3
2 4 5
0 1 2
2 2 3
2 1 4
3 3 5

Sample Output

3
2
2
invalid request!

HINT

10% 测试数据满足N<=8000,Q<=3000,

40% 测试数据满足所有询问中1<=K<=5 。即路由器的延迟时间不会发生变化。

100% 测试数据满足N,Q<=80000,任意一个路由器在任何时刻都满足延迟时间小于10^8。对于所有询问满足0<=K<=N 。

树链剖分+线段树套平衡树(treap)

通过树链剖分把查询操作映射到线段树上，线段树的每个结点建一棵以权值为关键字的treap，然后求区间第k大即可。

求法与【BZOJ 3196】二逼平衡树（Getnum）一样。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define pb push_back
#define N 100005
using namespace std;
int r=0,num=0,tot=0,root[20*N],top[N],siz[N],fa[N],id[N],t[N],tt[N],dep[N],son[N]; //注意root数组大小
vector<int> v[N];
struct treap
{
	int data,l,r,fix,size,weight;   //weight表示与当前结点权值相同的有几个
}a[20*N];
int n,q;
void Dfs1(int x,int f,int de)
{
	siz[x]=1;
	fa[x]=f;
	dep[x]=de;
	son[x]=0;
	for (int i=0;i<v[x].size();i++)
		if (v[x][i]!=f)
		{
			int u=v[x][i];
			Dfs1(u,x,de+1);
			siz[x]+=siz[u];
			if (siz[son[x]]<siz[u])
				son[x]=u;
		}
}
void Dfs2(int x,int tp)
{
	top[x]=tp;
	id[x]=++num;
	if (son[x]) Dfs2(son[x],tp);
	for (int i=0;i<v[x].size();i++)
	{
		int u=v[x][i];
		if (u==fa[x]||u==son[x]) continue;
		Dfs2(u,u);
	}
}
void Push_up(int x)
{
	a[x].size=a[a[x].r].size+a[a[x].l].size+a[x].weight;
}
void zag(int &x)
{
	int o=a[x].l;
	a[x].l=a[o].r;
	a[o].r=x;
	a[o].size=a[x].size;
	Push_up(x);
	x=o;
}
void zig(int &x)
{
	int o=a[x].r;
	a[x].r=a[o].l;
	a[o].l=x;
	a[o].size=a[x].size;
	Push_up(x);
	x=o;
}
void New_node(int &x,int data)
{
	x=++tot;
	a[x].l=a[x].r=0;
	a[x].size=a[x].weight=1;
	a[x].fix=rand();
	a[x].data=data;
}
void Insert(int &x,int data)
{
	if (!x)
	{
		New_node(x,data);
		return;
	}
	a[x].size++;
	if (data==a[x].data)
	{
		a[x].weight++;
		return;
	}
	if (data<a[x].data) 
	{
		Insert(a[x].l,data);
		if (a[a[x].l].fix<a[x].fix) zag(x);
	}
	else 
	{
		Insert(a[x].r,data);
		if (a[a[x].r].fix<a[x].fix) zig(x);
	}
}
void Build(int x,int l,int r,int now)
{
	Insert(root[x],tt[now]);
	if (l==r) return;
	int m=(l+r)>>1;
	if (now<=m) Build(x<<1,l,m,now);
	else Build(x<<1|1,m+1,r,now);
}
void Delet(int &x,int data)
{
	if (a[x].data==data)
	{
		if (a[x].weight>1)
		{
			a[x].weight--;  //size,weight都要减！！
			a[x].size--;
			return;
		}
		if (a[x].l*a[x].r==0) x=a[x].l+a[x].r;
		else if(a[a[x].l].fix<a[a[x].r].fix)
		{
			zag(x);
			Delet(x,data);
		}
		else 
		{
			zig(x);
			Delet(x,data);
		}
		return;
	}
	a[x].size--;
	if (a[x].data>data) Delet(a[x].l,data);
	else Delet(a[x].r,data);
}
void Modify(int x,int l,int r,int p,int pre,int now)
{
	Delet(root[x],pre);
	Insert(root[x],now);
	if (l==r) return;
	int m=(l+r)>>1;
	if (p<=m) Modify(x<<1,l,m,p,pre,now);
	else Modify(x<<1|1,m+1,r,p,pre,now);
}
void Askrank(int x,int data)
{
	if (!x) return;
	if (data==a[x].data)
	{
		r+=a[a[x].r].size;
		return;
	}
	if (data>a[x].data) Askrank(a[x].r,data);
	else 
	{
		r=r+a[a[x].r].size+a[x].weight;
		Askrank(a[x].l,data);
	}
}
void Getrank(int x,int lx,int rx,int l,int r,int data)
{
	if (lx>=l&&rx<=r)
	{
		Askrank(root[x],data);
		return;
	}
	int m=(lx+rx)>>1;
	if (l<=m) Getrank(x<<1,lx,m,l,r,data);
	if (r>m) Getrank(x<<1|1,m+1,rx,l,r,data);
}
void Query(int u,int v,int data)
{
	r=1;
	int tp1=top[u],tp2=top[v];
	while (tp1!=tp2)
	{
		if (dep[tp1]<dep[tp2]) swap(tp1,tp2),swap(u,v);
		Getrank(1,1,n,id[tp1],id[u],data);
		u=fa[tp1];
		tp1=top[u];
	}
	if (u==v) 
	{
		if (t[u]>data) r+=1;
		return;
	}
	if (dep[u]<dep[v]) swap(u,v);
	Getrank(1,1,n,id[v],id[u],data);
}
int Findkth(int u,int v,int k)
{
	Query(u,v,-1);
	if (r<=k) return -1;
	int ans,l=0,rr=100000000;
	while (l<=rr)
	{
		int m=(l+rr)>>1;
		Query(u,v,m);
		if (r<=k) ans=m,rr=m-1;
		else l=m+1;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
		scanf("%d",&t[i]);
	for (int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].pb(y),v[y].pb(x);
	}
	Dfs1(1,0,1);
	num=0;
	Dfs2(1,1);
	for (int i=1;i<=n;i++)
		tt[id[i]]=t[i];
	for (int i=1;i<=n;i++)
		Build(1,1,n,i);
	while (q--)
	{
		int k,x,y;
		scanf("%d%d%d",&k,&x,&y);
		if (!k)
		{
			Modify(1,1,n,id[x],t[x],y);
			t[x]=y;
		}
		else
		{
			int ans=Findkth(x,y,k);
			if (ans==-1) printf("invalid request!\n");
			else printf("%d\n",ans);
		}
	}
	return 0;
}