题解

思路概述

图中所有节点一开始互不连通，需要支持按连通块/单点/全局增量及最大值查询。若直接维护每个点的真实权值，U/A2/A3 会导致整块修改，A1 又要求能够快速把某个点从所属连通块的最大值结构中删除再插入。因此可以为每个连通块维护一个左偏堆（大根），堆里保存该块内所有节点的“真实值减去本块与全局懒标记”的结果；再配合并查集维护块代表以及每块的懒加标记。

• val[x]：节点在去掉所有懒标记后的值。
• add[root]：该连通块内所有节点的附加值，表示执行 A2 时的懒标记。
• madd：全局加法标记，表示执行 A3 后的增量。
• 每个联通块的堆根即为当前块内的最大节点，使用左偏堆可以在 O(log n) 时间内完成合并和删除。
• 另用 multiset 维护所有块根的 val[root] + add[root]，便于回答 F3。

各操作实现

1. 并查集 + 左偏堆合并 (U)：
   • 通过并查集找到两个块的堆根，若已在同一块则忽略。
   • 将节点数少的块合并到大的块，合并前把它的 add 差值 push_down 到整堆，使两个堆处于同一“基准系”。
   • 左偏堆 merge 过程中会始终保持堆根是块内最大值；合并完毕后更新块大小、懒标记并在 multiset 中删除旧根、插入新根。
2. 单点加 (A1)：
   • 需要把节点从所属堆中删除、修改值后重新插入。erase(x,v) 通过沿着父指针将 x 脱离堆，再在 val[x] 上加 v 后调用 merge 把它放回堆中即可。
3. 整块加 (A2)：
   • 在块代表上直接累加 add[root]+=v，并用 multiset 更新该块的最大值即可。
4. 全局加 (A3)：
   • 累加 madd，其它结构都不需变化。
5. 查询：
   • F1 x：返回 madd + add[find(x)] + val[x]。
   • F2 x：所在块的最大值即堆根，答案为 madd + add[root] + val[root]。
   • F3：multiset 里储存的是所有块根的当前最大值，输出 madd + *st.rbegin()。

各种堆操作都保持在 O(log n) 复杂度，并查集合并同样只需均摊 α(n)。因此总复杂度 O((n+Q) \log n)，内存 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, q, val[N], fa[N], ch[N][2], d[N], sz[N], f[N], add[N], madd;
int& rs(int x) {
  return ch[x][d[ch[x][1]] < d[ch[x][0]]];
}

multiset<int> st;
int find(int x) {
  return (x == f[x]) ? x : f[x] = find(f[x]);
}
void push_down(int x, int v) {
  val[x] += v;
  (ch[x][0]) && (push_down(ch[x][0], v), 1);
  (ch[x][1]) && (push_down(ch[x][1], v), 1);
}
void push_up(int x) {
  if (!x) {
    return;
  }
  if (d[x] != d[rs(x)] + 1) {
    d[x] = d[rs(x)] + 1;
    push_up(fa[x]);
  }
}
int merge(int x, int y) {
  if (!x || !y) {
    return x + y;
  }
  (val[x] < val[y]) && (swap(x, y), 1);
  fa[rs(x) = merge(rs(x), y)] = x;
  push_up(x);
  return x;
}
void cle(int x) {
  ch[x][0] = ch[x][1] = fa[x] = 0, d[x] = 1;
}
void Union(int x, int y) {
  if ((!x) || (!y) || (x == y)) {
    return;
  }
  (sz[x] < sz[y]) && (swap(x, y), 1);
  push_down(y, add[y] - add[x]);
  f[x] = f[y] = merge(x, y);
  if (f[x] == x) {
    st.erase(st.find(val[y] + add[x]));
    sz[x] += sz[y], sz[y] = add[y] = 0;
  } else {
    st.erase(st.find(val[x] + add[x]));
    sz[y] += sz[x], add[y] = add[x], sz[x] = add[x] = 0;
  }
}

int erase(int x,int v) {
  int rt = find(x), y;
  if (x == rt){
  	fa[ch[x][0]] = fa[ch[x][1]] = 0;
  	y = merge(ch[x][0],ch[x][1]);
  	st.erase(st.find(val[x] + add[x]));
  	val[x] += v,cle(x);
  	f[x] = f[y] = merge(x,y);
  	st.insert(val[f[x]] + add[x]);
  	if (f[x] == y){
  		add[y] = add[x],sz[y] = sz[x],add[x] = sz[x] = 0;
		}
	} 
	
	else{
		fa[ch[x][0]] = fa[ch[x][1]] = fa[x];
		ch[fa[x]][x == ch[fa[x]][1]] = merge(ch[x][0],ch[x][1]);
		val[x] += v,cle(x);
		y = find(x);
		f[x] = f[y] = merge(x,y);
		if (f[x] == x){
			st.erase(st.find(val[y] + add[y]));
			st.insert(val[x] + add[y]);
			add[x] = add[y],sz[x] = sz[y],add[y] = sz[y] = 0;
		}
	}
  return y;
}
signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> val[i], sz[i] = d[i] = 1, f[i] = i;
    st.insert(val[i]);
  }
  for (cin >> q; q--;) {
    string s;
    int x, y, v;
    cin >> s;
    if (s == "U") {
      cin >> x >> y;
      Union(find(x), find(y));
    }
    if (s == "A1") {
      cin >> x >> v;
      erase(x,v);
    }
    if (s == "A2") {
      cin >> x >> v;
      x = find(x);
      st.erase(st.find(add[x] + val[x]));
      add[x] += v;
      st.insert(add[x] + val[x]);
    }
    if (s == "A3") {
      cin >> v, madd += v;
    }
    if (s == "F1") {
      cin >> x;
      cout << madd + add[find(x)] + val[x] << "\n";
    }
    if (s == "F2") {
      cin >> x;
      cout << madd + add[find(x)] + val[find(x)] << "\n";
    }
    if (s == "F3") {
      cout << madd + (*st.rbegin()) << "\n";
    }
  }
}
/*
鏈€澶у€?
*/