HNOI 2016 网络（树链剖分+线段树+堆）

发表于 |
字数统计: 2,032字 | 阅读时长 ≈ 10min

[Hnoi2016 day1]网络

问题描述

一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。由于这条路径是唯一的，当路径上的某个服务器出现故障，无法正常运行时，数据便无法交互。此外，每个数据交互请求都有一个重要度，越重要的请求显然需要得到越高的优先处理权。现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也是很简单的，在每一个时刻，只有可能出现下列三种事件中的一种：1. 在某两个服务器之间出现一条新的数据交互请求；2. 某个数据交互结束请求；3. 某个服务器出现故障。系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后，这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。你的任务是在每次出现故障时，维护未被影响的请求中重要度的最大值。注意，如果一个数据交互请求已经结束，则不将其纳入未被影响的请求范围。

输入格式

第一行两个正整数n,m，分别描述服务器和事件个数。服务器编号是从1开始的，因此n个服务器的编号依次是1,2,3,…,n。接下来n-1行，每行两个正整数u,v，描述一条树边。u和v是服务器的编号。接下来m行，按发生时刻依次描述每一个事件；即第i行（i=1,2,3,…,m）描述时刻i发生的事件。每行的第一个数type描述事件类型，共3种类型：（1）若type=0，之后有三个正整数a,b,v，表示服务器a,b之间出现一条重要度为v的数据交互请求；（2）若type=1，之后有一个正整数t，表示时刻t（也就是第t个发生的事件）出现的数据交互请求结束；（3）若type=2，之后有一个正整数x，表示服务器x在这一时刻出现了故障。对于每个type为2的事件，就是一次询问，即询问“当服务器x发生故障时，未被影响的请求中重要度的最大值是多少？”注意可能有某个服务器自身与自身进行数据交互的情况。$2 ≤ n ≤ 10^5, 1 ≤ m ≤ 2×10^5$，其他的所有输入值不超过$ 10^9$

输出格式

对于每个type=2的事件，即服务器出现故障的事件，输出一行一个整数，描述未被影响的请求中重要度的最大值。如果此时没有任何请求，或者所有请求均被影响，则输出-1。

样例输入

13 23

1 2

1 3

2 4

2 5

3 6

3 7

4 8

4 9

6 10

6 11

7 12

7 13

2 1

0 8 13 3

0 9 12 5

2 9

2 8

2 2

0 10 12 1

2 2

1 3

2 7

2 1

0 9 5 6

2 4

2 5

1 7

0 9 12 4

0 10 5 7

2 1

2 4

2 12

1 2

2 5

2 3

样例输出

-1

3

5

-1

1

-1

1

1

3

6

7

7

4

6

本题需要维护的是不经过某个点的路径最大值，这是可以维护的，考虑树链剖分，然后每次修改是一条链，那么就只需要更新这条链以外的点就行了。

具体实现时，将这条链上的区间取出来，排序之后在线段树上修改两两区间之间的位置就好了。由于一条路径最多被拆成$\log n$条重链，因此最多只有$\log n$个区间需要修改，复杂度并没有上升。

然后线段树上需要维护每个位置的最大值，并且要支持插入删除操作，因此每个位置上开两个堆，一个记录插入，一个记录删除即可。区间修改的时候$lazy$不需要下放，只用在查询的时候自底向下取每一层$lazy$的最大值就行了。

注意到添加和删除一个数操作的区间一定是相同的，因此不会出现删除到不存在的数的情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define N 800005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
int G() {
	int o=0;char t=GC;
	while(!isdigit(t)) t=GC;
	while(isdigit(t)) o=o*10+t-48,t=GC;
	return o;
}
struct nodd{int x,y;};
bool operator<(nodd a,nodd b)
{return a.y<b.y;}
struct node
{
	priority_queue<int>Q[2];
	void Ins(int x,int ty){Q[ty].push(x);}
	int top()
	{
		while(Q[0].size()&&Q[1].size()&&Q[0].top()==Q[1].top())Q[0].pop(),Q[1].pop();
		if(Q[0].size())return Q[0].top();
		return -1;
	}
}v[N];
int n,m,X[N],Y[N],Z[N];
int son[N],fa[N],top[N],dep[N],si[N],id[N],VT;
int TOT,LA[N],NE[N],EN[N];
int tot,ls[N],rs[N];
void add(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void FHE(int x,int f)
{
	int i,y;
	fa[x]=f;dep[x]=dep[f]+1;si[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(y==f)continue;
		FHE(y,x);si[x]+=si[y];
		if(si[y]>=si[son[x]])son[x]=y;
	}
}
void CHE(int x,int f)
{
	int i,y;
	top[x]=f;id[x]=++VT;
	if(son[x])CHE(son[x],f);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(y==fa[x])continue;
		if(y!=son[x])CHE(y,y);
	}
}
int BT(int x,int y)
{
	int p=++tot;
	if(x<y)
	{
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
	}
	return p;
}
void ADD(int p,int l,int r,int x,int y,int d,int ty)
{
	if(x<=l&&y>=r){v[p].Ins(d,ty);return;}
	int mid=l+r>>1;
	if(x<=mid&&y>=l)ADD(ls[p],l,mid,x,y,d,ty);
	if(x<=r&&y>mid)ADD(rs[p],mid+1,r,x,y,d,ty);
}
int GA(int p,int l,int r,int x)
{
	if(l==r)return v[p].top();
	int mid=l+r>>1,tmp;
	tmp=x<=mid?GA(ls[p],l,mid,x):GA(rs[p],mid+1,r,x);
	return max(tmp,v[p].top());
}
void MD(int x,int y,int d,int ty)
{
	vector<nodd>S;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		S.push_back((nodd){id[top[x]],id[x]});x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	S.push_back((nodd){id[y],id[x]});
	sort(S.begin(),S.end());
	int l=0,r=S.size()-1;
	if(S[l].x!=1)ADD(1,1,n,1,S[l].x-1,d,ty);
	if(S[r].x!=n)ADD(1,1,n,S[r].y+1,n,d,ty);
	for(int i=l;i<r;i++)if(S[i].y<S[i+1].x-1)ADD(1,1,n,S[i].y+1,S[i+1].x-1,d,ty);
}
int main_main()
{
	int i,j,k,x,y,z;
	n=G();m=G();
	for(i=1;i<n;i++)
	{
		x=G();y=G();
		add(x,y);add(y,x);
	}
	FHE(1,0);CHE(1,1);BT(1,n);
	for(i=1;i<=m;i++)
	{
		k=G();
		if(k==0)
		{
			x=G();y=G();z=G();
			X[i]=x;Y[i]=y;Z[i]=z;
			MD(x,y,z,0);
		}
		else if(k==1)
		{
			x=G();
			MD(X[x],Y[x],Z[x],1);
		}
		else
		{
			x=G();
			printf("%d\n",GA(1,1,n,id[x]));
		}
	}
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}