http://www.lydsy.com/JudgeOnline/problem.php?id=2333
读入所有数据, 先模拟一遍所有的合并操作
我们不关心联通块长什么样, 只关心联通块内有谁
所以可以把一个联通块用一个链表存储
合并 x 和 y 时, y 的链表整体接到 x 的链表后面
这样就成了线性结构
按照链表顺序重新给序列标号即可用线段树维护
一遍过,^_^
#include < cstdio > #include < iostream > #include < algorithm > using namespace std;#define N 300001 int a[N];
struct Data {
char s[3];
int x,
y;
}
data[N];
int fa[N],
nxt[N],
ed[N];
int id[N],
dy[N];
int mx[N << 2],
f[N << 2];
int ans;
void read(int & x) {
x = 0;
int f = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
x *= f;
}
void build(int k, int l, int r) {
if (l == r) {
mx[k] = a[id[l]];
return;
}
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
}
void down(int k) {
mx[k << 1] += f[k];
mx[k << 1 | 1] += f[k];
f[k << 1] += f[k];
f[k << 1 | 1] += f[k];
f[k] = 0;
}
void add(int k, int l, int r, int opl, int opr, int w) {
if (l >= opl && r <= opr) {
f[k] += w;
mx[k] += w;
return;
}
if (f[k]) down(k);
int mid = l + r >> 1;
if (opl <= mid) add(k << 1, l, mid, opl, opr, w);
if (opr > mid) add(k << 1 | 1, mid + 1, r, opl, opr, w);
mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
}
void query(int k, int l, int r, int opl, int opr) {
if (l >= opl && r <= opr) {
ans = max(ans, mx[k]);
return;
}
if (f[k]) down(k);
int mid = l + r >> 1;
if (opl <= mid) query(k << 1, l, mid, opl, opr);
if (opr > mid) query(k << 1 | 1, mid + 1, r, opl, opr);
}
int find(int i) {
return fa[i] == i ? i: fa[i] = find(fa[i]);
}
int main() {
int n,
m;
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= n; ++i) fa[i] = i,
ed[i] = i;
char s[5];
int x,
y;
int fx,
fy;
read(m);
for (int i = 1; i <= m; ++i) {
scanf("%s", data[i].s);
if (! (data[i].s[0] == 'F' && data[i].s[1] == '3')) read(data[i].x);
if (data[i].s[0] == 'U' || data[i].s[0] == 'A' && data[i].s[1] != '3') read(data[i].y);
if (data[i].s[0] == 'U') {
fx = find(data[i].x);
fy = find(data[i].y);
nxt[ed[fx]] = fy;
ed[fx] = ed[fy];
fa[fy] = fx;
}
}
int tot = 0;
for (int i = 1; i <= n; ++i) if (find(i) == i) {
int j = i;
while (j != ed[i]) {
id[++tot] = j;
dy[j] = tot;
j = nxt[j];
}
id[++tot] = j;
dy[j] = tot;
}
build(1, 1, n);
for (int i = 1; i <= n; ++i) fa[i] = i,
ed[i] = i;
int all = 0;
for (int i = 1; i <= m; ++i) {
if (data[i].s[0] == 'U') {
fx = find(data[i].x);
fy = find(data[i].y);
nxt[ed[fx]] = fy;
ed[fx] = ed[fy];
fa[fy] = fx;
} else if (data[i].s[0] == 'A') {
if (data[i].s[1] == '1') add(1, 1, n, dy[data[i].x], dy[data[i].x], data[i].y);
else if (data[i].s[1] == '2') add(1, 1, n, dy[find(data[i].x)], dy[ed[find(data[i].x)]], data[i].y);
else all += data[i].x;
} else {
if (data[i].s[1] == '1') {
ans = -1e9;
query(1, 1, n, dy[data[i].x], dy[data[i].x]);
printf("%d\n", ans + all);
} else if (data[i].s[1] == '2') {
ans = -1e9;
query(1, 1, n, dy[find(data[i].x)], dy[ed[find(data[i].x)]]);
printf("%d\n", ans + all);
} else printf("%d\n", mx[1] + all);
}
}
}
来源: http://www.bubuko.com/infodetail-2481478.html