bzoj 1146: [CTSC2008]网络管理Network （树上带修改主席树）

程序员文章站 2024-03-03 16:53:28

...

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大的路由器的延迟时间。

注意N,Q<=80000,任意一个路由器在任何时刻都满足延迟时间小于10^8。

对于所有询问满足0<=K<=N

Output

对于每一个第二种询问（k>0），输出一行。包含一个整数为相应的延迟时间。

如果路径上的路由器不足k个，则输出信息“invalidrequest!”

（全部小写不包含引号，两个单词之间有一个空格）。

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

Source

思路：

这个题一开始没有建一个静态的主席树，就是一开始插入点的时候就用树状数组维护。

一开始就用树状数组维护，缺点就是时间复杂化会大，空间也要很大，

但是 update 有个小技巧。就是用当前版本的线段树更新当前版本的线段树的时候，可以不用新开点。具体见代码。

在这个题中，带修改的树上主席树，

用的dfs 序还有 lca，

我们想一下，在树上修改，会影响那些值呢？，肯定会影响当前节点的孩子。因为每个点，肯定是从这个点的父亲节点过来的。

所以我们就需要修改每个点的孩子。这个要怎么修改呢，当然是dfs 序，维护当前点的所有孩子。

然后用树状数组 +1 -1.

最后询问的时候，[l,r] 左孩子有多少个数，

rt[r] + rt[l] - rt[lca(l,r)] - rt[f[lca(l,r)][0]];
这里的 rt 代表的是，树状数组中维护的从根节点到当前节点有多少个数。

#include<bits/stdc++.h>
#define low(x) (x & (-x))
using namespace std;
const int N = 8e4+100;
const int M = N*120;
int rt[N*2],ls[M],rs[M],sum[M],sz;
int n,m,t[N],s[N*2],top;
int K[N],A[N],B[N],L[2][N],R[2][N];
int Head[N],Next[N*4],To[N*4],cnt;
int in[N],out[N],tim;
int dep[N],f[N][20];
void add(int u, int v){
	Next[++cnt] = Head[u];
	To[cnt] = v;
	Head[u] = cnt;
}
void dfs(int u, int father){
	in[u] = ++tim; f[u][0] = father; dep[u] = dep[father] + 1;
	for (int i = 1; i < 20; ++i) f[u][i] = f[f[u][i-1]][i-1];
	for (int i = Head[u]; i; i = Next[i]){
		if (To[i] == father) continue; 
		dfs(To[i],u);
	}
	out[u] = tim+1;
}

int lca(int x,int y){
	if (dep[x] < dep[y]) swap(x,y);
	for (int i = 19; i>= 0; i--) if (dep[f[x][i]] >= dep[y]) x = f[x][i];
	if (x == y) return x;
	for (int i = 19; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
	return f[x][0];
}
void update(int &now, int l, int r, int k, int c){
	if (!now) now = ++sz; 
	sum[now] += c;
	if (l + 1 == r) return;
	int mid = (l + r) >> 1;
	if (k < mid) update(ls[now],l,mid,k,c);
	if (k >= mid) update(rs[now],mid,r,k,c);
}

int query(int l, int r, int k){
	if (l + 1 == r) return l;
	int sum1 = 0, sum2 = 0;
	for (int i = 0; i < 2; ++i)
		for (int j = 1; j <= L[i][0]; ++j)
			sum1 += sum[ls[L[i][j]]];
	for (int i = 0; i < 2; ++i)
		for (int j = 1; j <= R[i][0]; ++j)
			sum2 += sum[ls[R[i][j]]];
	int temp = sum1 - sum2, mid = (l + r) / 2;
	// printf("%d %d %d %d\n",l,r,temp,k);
	if (temp >= k){
		for (int i = 0; i < 2; ++i)
			for (int j  = 1; j <= L[i][0]; ++j)
				L[i][j] = ls[L[i][j]];
		for (int i = 0; i < 2; ++i)
			for (int j = 1; j <= R[i][0]; ++j)
				R[i][j] = ls[R[i][j]];
		return query(l,mid,k);
	} else{
		for (int i = 0; i < 2; ++i)
			for (int j  = 1; j <= L[i][0]; ++j)
				L[i][j] = rs[L[i][j]];
		for (int i = 0; i < 2; ++i)
			for (int j = 1; j <= R[i][0]; ++j)
				R[i][j] = rs[R[i][j]];
		return query(mid,r,k-temp);
	}
}

void ask(int a, int b, int k ){
	int tt = lca(a,b);
	if (dep[a] + dep[b] - 2 * dep[tt] + 1 < k) {
		puts("invalid request!");
		return;
	}
	k = dep[a] + dep[b] - 2*dep[tt] + 2 - k;
	L[0][0] = L[1][0] = 0; R[0][0] = R[1][0] = 0;
	for (int i = in[a]; i; i -= low(i)) L[0][++L[0][0]] = rt[i];
	for (int i = in[b]; i; i -= low(i)) L[1][++L[1][0]] = rt[i];
	for (int i = in[tt]; i; i -= low(i)) R[0][++R[0][0]] = rt[i];
	for (int i = in[f[tt][0]]; i; i -= low(i)) R[1][++R[1][0]] = rt[i];
	int temp = query(1,top+1,k);
	// printf("%d\n",temp);
	printf("%d\n",s[temp]);
}

void renew(int x,int y,int val){
	for (int i = x; i <= n; i += low(i))
		update(rt[i],1,top+1,y,val);
}
void init(){
	int x,y;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; ++i)
		scanf("%d",&t[i]),s[++top] = t[i];
	for (int i = 1; i < n; ++i){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for (int  i = 0; i < m; ++i){
		scanf("%d%d%d",&K[i],&A[i],&B[i]);
		if (!K[i]) s[++top] = B[i];
	}
	sort(s+1,s+top+1);
	top = unique(s+1,s+top+1) - s - 1;
	dfs(1,0);
	for (int i = 1; i <= n; ++i){
		int tt = lower_bound(s+1,s+top+1,t[i]) - s;
		renew(in[i],tt,1);
		renew(out[i],tt,-1);
	}
}
void solve(){
	for (int i = 0; i < m; ++i){
		if (!K[i]){
			int tt = lower_bound(s+1,s+top+1,t[A[i]]) - s;
			renew(in[A[i]],tt,-1); renew(out[A[i]],tt,1);
			tt = lower_bound(s+1,s+top+1,B[i]) - s;
			renew(in[A[i]],tt,1); renew(out[A[i]],tt,-1);
			t[A[i]] = B[i];
		} else ask(A[i],B[i],K[i]);
	}
}

int main(){
	init();
	solve();
	return 0;
}