题目描述

某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。为了让同学们更好地监督自己,学校推行了刷卡机制。学校中有$n$个地点,用$1$到$n$的整数表示,每个地点设有若干个刷卡机。有以下三类事件:

  1. 修建了一条连接A地点和B地点的跑道。
  2. A点的刷卡机台数变为了B。
  3. 进行了一次长跑。问一个同学从A出发,最后到达B最多可以刷卡多少次。具体的要求如下:

当同学到达一个地点时,他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次,即使多次到达同一地点也不能多次刷卡。为了安全起见,每条跑道都需要设定一个方向,这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向,按照任意路径从A地点到B地点能刷卡的最多次数。

输入格式

输入的第一行包含两个正整数$n,m$,表示地点的个数和操作的个数。

第二行包含$n$个非负整数,其中第$i$个数为第个地点最开始刷卡机的台数。

接下来有$m$行,每行包含三个非负整数$P,A,B$,$P$为事件类型,$A,B$为事件的两个参数。

最初所有地点之间都没有跑道。

每行相邻的两个数之间均用一个空格隔开。表示地点编号的数均在$1$到$n$之间,每个地点的刷卡机台数始终不超过$10000$,$P=1,2,3$。

输出格式

输出的行数等于第3类事件的个数,每行表示一个第3类事件。如果该情况下存在一种设定跑道方向的方案和路径的方案,可以到达,则输出最多可以刷卡的次数。如果A不能到达B,则输出$-1$。

题解

LCT维护边双连通分量

说是叫边双连通分量,其实就是在连边导致产生环时把环缩成一个点

例如此题,显然,如果进入了一个环的某个点,那么就一定能把这个环上所有点全部走完,然后再从任意一个点出去

所以可以把所有环缩成点,点权为环上所有点权之和,这样原图就变成了一棵树,每次直接查询A所在的环到B所在的环之间路径的点权和即可

然后此题就做完了

实现也非常简单,可以开并查集来记录两个点是否在同一个边双里,大部分操作与普通的LCT无异,但是有一些细节:

  1. LCT内部维护一个并查集记录两个点是否在同一个边双内,外部还要维护一个并查集记录两个点当前是否联通

  2. access时跳父亲要跳到find(fa[x])上,更改重儿子时还要记得把新的重儿子的父亲设为自己!

  3. 如果在两点之间连边时,两点已在同一棵树中,但不在同一个边双中,则要把两点之间的路径上的点合并为一个点:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    inline void merge(int x, int y) {
    split(x, y);
    q.push(y);
    while (!q.empty()) {
    int u = q.front(); q.pop();
    Fa[find(u)] = y;
    if (ch[u][0]) q.push(ch[u][0]);
    if (ch[u][1]) q.push(ch[u][1]);
    ch[u][0] = ch[u][1] = 0; //把儿子清零避免pushup时出错!
    }
    val[y] = sum[y];
    }
  4. 进行任何操作时(例如link,split),都是对find(x)进行修改,而不是$x$!

更多细节详见代码

代码

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
#include <bits/stdc++.h>
#define N 150005
using namespace std;

inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
return x * f;
}

namespace LCT{
int Fa[N], fa[N], ch[N][2], sum[N], val[N], tag[N];

int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); }
inline bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline void pushup(int x) { sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x]; }
inline void rev(int x) { swap(ch[x][0], ch[x][1]); tag[x] ^= 1; }
inline void pushdown(int x) {
if (!tag[x]) return; tag[x] = 0;
if (ch[x][0]) rev(ch[x][0]); if (ch[x][1]) rev(ch[x][1]);
}
inline void rotate(int x) {
int y = fa[x], z = fa[y], k = (ch[y][1]==x);
if (!isroot(y)) ch[z][ch[z][1]==y] = x;
fa[x] = z;
ch[y][k] = ch[x][!k]; fa[ch[x][!k]] = y;
ch[x][!k] = y; fa[y] = x;
pushup(y); pushup(x);
}
int stk[N], top;
inline void splay(int x) {
stk[top=1] = x;
for (int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];
while (top) pushdown(stk[top--]);
while (!isroot(x)) {
int y = fa[x], z = fa[y];
if (!isroot(y)) ((ch[y][1]==x)^(ch[z][1]==y)) ? rotate(x) : rotate(y);
rotate(x);
}
}
inline void access(int x) {
for (int i = 0; x; i = x, x = find(fa[x])) {
splay(x); ch[x][1] = i;
if (i) fa[i] = x;
pushup(x);
}
}
inline void makeroot(int x) {
access(x); splay(x); rev(x);
}
inline void split(int x, int y) {
makeroot(x); access(y); splay(y);
}
inline void link(int x, int y) {
makeroot(x); fa[x] = y;
}
queue<int> q;
inline void merge(int x, int y) {
split(x, y);
q.push(y);
while (!q.empty()) {
int u = q.front(); q.pop();
Fa[find(u)] = y;
if (ch[u][0]) q.push(ch[u][0]);
if (ch[u][1]) q.push(ch[u][1]);
ch[u][0] = ch[u][1] = 0;
}
val[y] = sum[y];
}
}

int n, m, Fa[N], a[N];

int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); }
void Link(int x, int y) {
int fx = LCT::find(x), fy = LCT::find(y);
if (fx == fy) return;
int u = find(x), v = find(y);
if (u != v) {
Fa[u] = v;
LCT::link(fx, fy);
} else {
LCT::merge(fx, fy);
}
}

int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = LCT::val[i] = read();
for (int i = 1; i <= n; i++) Fa[i] = LCT::Fa[i] = i;
for (int i = 1, tp, x, y; i <= m; i++) {
tp = read(); x = read(); y = read();
if (tp == 1) {
Link(x, y);
} else if (tp == 2) {
int v = y - a[x];
a[x] = y;
int fx = LCT::find(x);
LCT::makeroot(fx);
LCT::val[fx] += v;
LCT::pushup(fx);
} else {
if (find(x) != find(y)) puts("-1");
else {
int fx = LCT::find(x), fy = LCT::find(y);
LCT::split(fx, fy);
printf("%d\n", LCT::sum[fy]);
}
}
}
return 0;
}

评论