目录

  1. 引言
  2. UOJ #274. 【清华集训2016】温暖会指引我们前行
    1. 任务描述
    2. 输入格式
    3. 输出格式
    4. 样例一
      1. input
      2. output
    5. 样例二
      1. input
      2. output
    6. 样例三
    7. 限制与约定
    8. 下载
    9. 题目分析
    10. 代码

引言

UOJ #274. 【清华集训2016】温暖会指引我们前行 题解

UOJ #274. 【清华集训2016】温暖会指引我们前行

寒冬又一次肆虐了北国大地

无情的北风穿透了人们御寒的衣物

可怜虫们在冬夜中发出无助的哀嚎

“冻死宝宝了!”

这时

远处的天边出现了一位火焰之神

“我将赐予你们温暖和希望!”

只见他的身体中喷射出火焰之力

通过坚固的钢铁,传遍了千家万户

这时,只听见人们欢呼

“暖气来啦!”

任务描述

虽然小R住的宿舍楼早已来了暖气,但是由于某些原因,宿舍楼中的某些窗户仍然开着(例如厕所的窗户),这就使得宿舍楼中有一些路上的温度还是很低。

小R的宿舍楼中有$n$个地点和一些路,一条路连接了两个地点,小R可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始,小R还不熟悉宿舍楼中的任何一条路,所以他会慢慢地发现这些路,他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。

小R需要在宿舍楼中活动,每次他都需要从一个地点到达另一个地点。小R希望每次活动时经过一条最温暖的路径,最温暖的路径的定义为,将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高,在满足该条件的情况下,温度第二低的路温度尽量高,以此类推。小R不会经过重复的路。由于每条路的温度互不相同,因此只存在一条最温暖的路径。

对于小R的每次活动,你需要求出小R需要走过的路径总长度。如果小R通过当前发现的路不能完成这次活动,则输出 $-1$。

注意本题中的字典序与传统意义上的字典序定义有所不同,对于两个序列$a,b(a \neq b)$,若$a$是$b$的前缀则$a$的字典序较大,同时可以推出空串的字典序最大。

输入格式

第一行两个正整数 $n,m$。表示小R的宿舍楼中有 $n$ 个地点,共发生了 $m$ 个事件。

接下来 $m$ 行,每行描述一个事件,事件分为三类。

  1. $\texttt{find id u v t l}$ 表示小R发现了一条连接$u$和$v$之间的路,编号为$id$。相同$id$的边只会出现一次。

  2. $\texttt{move u v}$ 表示小R要从$u$到达$v$,你需要计算出最温暖的路径的长度 ,若不能从$u$到达$v$,则输出$-1$。

  3. $\texttt{change id l}$ 表示从$u$到$v$这条边的长度变为了$l$(保证在当前时间点这条边存在)。

输出格式

对于每个询问,输出一行整数,表示最温暖的路径长度。

样例一

input

8 19
find 0 0 2 7 2
find 1 2 4 4 4
find 2 4 6 10 1
find 3 6 7 8 6
move 2 7
move 1 6
find 4 2 5 3 4
move 0 5
change 0 12
find 5 4 5 5 10
find 6 2 3 6 9
move 3 5
find 7 0 1 12 1
move 1 6
find 8 1 7 11 100
move 1 6
move 3 7
move 5 6
move 2 2

output

11
-1
6
23
18
106
122
11
0

样例二

input

15 45
find 0 1 0 8 5987
find 1 2 0 14 5455
find 2 3 0 27 8830
find 3 4 3 42 7688
find 4 5 0 25 1756
find 5 6 5 35 1550
find 6 7 4 43 9440
move 3 9
change 2 9113
move 10 13
move 3 3
move 11 10
find 7 8 7 6 7347
find 8 9 8 26 8935
move 8 4
change 3 4466
find 9 10 9 28 8560
move 6 5
find 10 11 10 31 6205
change 9 9228
find 11 12 10 23 948
find 12 13 12 45 5945
move 0 9
move 2 5
change 2 6118
find 13 14 13 12 6906
move 4 1
change 2 504
find 14 4 2 22 9796
move 10 7
move 1 14
move 13 3
find 15 12 9 39 8985
find 16 9 8 17 3710
change 1 5370
find 17 1 0 36 4669
find 18 7 6 37 8087
move 9 0
find 19 14 9 33 8234
find 20 0 4 24 5209
change 1 4883
find 21 6 3 9 2461
find 22 5 2 19 4291
change 1 7219
change 6 4846

output

-1
-1
0
-1
16787
1550
39301
7211
16571
25510
59706
46309
30692

样例三

见样例数据下载

限制与约定

对于find操作:$(0\le id\lt m, 0\le u,v \lt n, u\ne v,0\le t\le 1000000000, 0 \le l \le 10000)$;

对于move操作:$(0\le u,v \lt n)$;

对于change操作:$(0 \le l \le 10000)$。

对于100%的数据,$1\le n\le 100000, 1\le m \le 300000$ 。

本题共有20个数据点,每个数据点5分。

测试点$n$$m$$其它$
$1-2$$\leq20$$\leq50$无特殊约定
$3-5$$\leq1000$$\leq3000$
$6-10$$\leq100000$$\leq300000$所有的find事件都在move事件之前,且没有change事件
$11-14$所有的find事件都在move事件之前
$15-20$无特殊约定

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载

题目分析

这道题,我们显然是要先维护一下当前温度的最大生成树,然后不断地向里面加边,替换已有的边,然后回答询问,大概就是这样的一个思路

我们发现,要查询和要维护的信息都在边上,但是LCT很难直接维护边信息,怎么办呢?可以使用加点法

我们新加入一些点,这些点的信息就是对应的边上的信息,就是说,我们是用这些新加入的点来代替原来的边的,假设原来的边的两端为$x$和$y$,那么这个新点就再和$x$, $y$连边即可

然后就和普通的LCT一样了,维护一下当前子树中点权最小的那个点即可

代码

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <stack>
#define maxn 600005
#define INF 2000000005
#define ls ch[x][0]
#define rs ch[x][1]
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
using namespace std;
int n, m;
struct edge{
int x, y, t, l;
edge(int x = INF, int y = INF, int t = INF, int l = INF) : x(x), y(y), t(t), l(l){}
}e[maxn];
int num[maxn];
int val[maxn];
int sum[maxn];
int fa[maxn];
int ch[maxn][2];
bool rev[maxn];
bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushup(int x){
sum[x] = sum[ls] + sum[rs] + val[x];
num[x] = x;
if (e[num[ls]].t < e[num[x]].t) num[x] = num[ls];
if (e[num[rs]].t < e[num[x]].t) num[x] = num[rs];
}
inline void pushdown(int x){
if (rev[x]){
rev[ls] ^= 1, rev[rs] ^= 1;
rev[x] = 0;
swap(ls, rs);
}
}
void rotate(int x, int d){
//printf("rotate start-----------------------\n");
int k = ch[x][d];
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
//printf("rotate end-----------------------\n");
}
stack<int> s;
void splay(int x){
//printf("splay start-----------------------\n");
int t = x;
while (!is_root(x)){
s.push(x);
x = fa[x];
if (x == fa[x]) printf("%d", x), assert(false);
}
s.push(x);
while (!s.empty()){
pushdown(s.top());
s.pop();
}
x = t;
while (!is_root(x)){
int f1 = fa[x];
int d1 = ch[f1][1] == x;
if (!is_root(f1)){
int f2 = fa[f1];
int d2 = ch[f2][1] == f1;
if (d1 ^ d2) rotate(f1, d1), rotate(f2, d2);
else rotate(f2, d2), rotate(f1, d1);
}
else rotate(f1, d1);
}
//printf("splay end-----------------------\n");
}
void access(int x){
//printf("access start-----------------------\n");
int t = 0;
while (x){
splay(x);
rs = t;
pushup(x);
t = x;
x = fa[x];
}
//printf("access end-----------------------\n");
}
void moveroot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}
void split(int x, int y){
moveroot(y);
access(x);
splay(x);
}
bool check(int x, int y){
access(x), splay(x);
while (ls) x = ls;
splay(x);
int f = x; x = y;
access(x), splay(x);
while (ls) x = ls;
splay(x);
return f == x;
}
int get_edge(int x, int y){
split(x, y);
return num[x];
}
void get_len(int x, int y){
if (!check(x, y)) {
printf("-1\n");
return;
}
split(x, y);
printf("%d\n", sum[x]);
}
void cut(int x, int y){
split(x, y);
fa[y] = ls = 0;
pushup(x);
}
void link(int id){
int x = e[id].x, y = e[id].y;
if (check(x, y)){
int k = get_edge(x, y);
if (e[k].t > e[id].t) return;
cut(k, e[k].x);
cut(k, e[k].y);
}
sum[id] = val[id] = e[id].l;
num[id] = id;
moveroot(x);
fa[x] = id;
moveroot(y);
fa[y] = id;
}
void modify(int id, int len){
access(id);
splay(id);
val[id] = len;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("warm.in", "r", stdin);
#endif
char op[15];
int x, y, z, w, id;
scanf("%d%d", &n, &m);
rep(i, 1, m){
scanf("%s", op);
switch(op[0]){
case 'f': scanf("%d%d%d%d%d", &id, &x, &y, &z, &w), id += n + 1, x++, y++, e[id] = edge(x, y, z, w), link(id); break;
case 'm': scanf("%d%d", &x, &y), x++, y++, get_len(x, y); break;
case 'c': scanf("%d%d", &id, &x), id += n + 1, modify(id, x); break;
default: assert(false); break;
}
}
return 0;
}