Description
有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：
U x y: 加一条边，连接第x个节点和第y个节点
A1 x v: 将第x个节点的权值增加v
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
A3 v: 将所有节点的权值都增加v
F1 x: 输出第x个节点当前的权值
F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值
F3: 输出所有节点中，权值最大的节点的权值
n.q <= 300000
Solution
这题题号真2333
首先考虑用并查集维护连通性.
单点加, 查. 全局加, 查. 都比较好实现, 主要是联通块维护.
考虑用线段树维护. 但线段树要求的区间是连续的. 如何解决?
考虑做树剖的时候查询子树的dfn是连续的, 我们考虑重新编号.
于是我们把操作离线. 然后先用并查集维护连通性, 把树建出来, 每个集合在合并时,就将这个集合的根节点设置为它的最后一个子树.然后来一波dfs求出每个点的dfs序.
然后就很好做了(我TM竟然没想出来)
因为最终的dfs序已经形成, 所以我们只要把询问重新用线段树模拟计算一遍就好了
注意并查集要维护当前集合的大小, 然后直接在线段树上操作区间$$[dfn[x], dfn[x] + size[x] - 1]$$即可, 然后在实际代码编写中并不要写dfs, 只要在合并集合时将被合并者的线段全体接到目标线段之后.
Inspiration
在维护集合连通性, 因为集合的依附关系可以用一棵树来表示. 所以, 我们如果要对联通块进行修改,查询.可以将操作离线. 再行用并查集森林的dfs序进行重新编号. 即可维护
Code:
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
typedef long long LL;
typedef long double LD;
int read() {
int x = 0, flag = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') flag *= -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - 48;
ch = getchar();
}
return x * flag;
}
void write(LL a) {
if(a >= 10) write(a / 10);
putchar(a % 10 + '0');
}
#define Maxn 300009
int n, a[Maxn];
int fa[Maxn], nxt[Maxn], tail[Maxn];
int find(int x) {
return x ^ fa[x] ? (fa[x] = find(fa[x])) : x;
}
struct operation {
int id, val1, val2;
}opt[Maxn];
int dfn[Maxn], unid[Maxn], size[Maxn], cnt;
namespace SGMT_tree {
int tree[Maxn << 3], tag[Maxn << 3];
#define lc(x) ((x) << 1)
#define rc(x) (((x) << 1) | 1)
void pushup(int root) {
tree[root] = max(tree[lc(root)], tree[rc(root)]);
}
void pushdown(int root) {
if(tag[root]) {
tree[lc(root)] += tag[root], tree[rc(root)] += tag[root];
tag[lc(root)] += tag[root], tag[rc(root)] += tag[root];
tag[root] = 0;
}
}
void build(int root, int l, int r) {
if(l > r) return ;
if(l == r) {
tree[root] = a[unid[l]];
return ;
}
int mid = (l + r) >> 1;
build(lc(root), l, mid);
build(rc(root), mid + 1, r);
pushup(root);
}
void modify(int root, int l, int r, int x, int y, int v) {
if(l > r || r < x || l > y) return ;
if(x <= l && r <= y) {
tree[root] += v, tag[root] += v;
return ;
}
int mid = (l + r) >> 1; pushdown(root);
modify(lc(root), l, mid, x, y, v);
modify(rc(root), mid + 1, r, x, y, v);
pushup(root);
}
int query(int root, int l, int r, int x, int y) {
if(l > r || r < x || l > y) return INT_MIN;
if(x <= l && r <= y) return tree[root];
int mid = (l + r) >> 1, res = INT_MIN; pushdown(root);
res = max(query(lc(root), l, mid, x, y), res);
res = max(query(rc(root), mid + 1, r, x, y), res);
return res;
}
}
char s[Maxn];
int main() {
#ifdef Qrsikno
freopen("BZOJ2333.in", "r", stdin);
freopen("BZOJ2333.out", "w", stdout);
#endif
n = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, n) fa[i] = tail[i] = i, nxt[i] = 0;
int q = read();
rep(i, 1, q) {
scanf("%s", s);
if(s[0] == 'U') opt[i].id = 0, opt[i].val1 = read(), opt[i].val2 = read();
if(s[0] == 'A') {
if(s[1] == '1') opt[i].id = -1, opt[i].val1 = read(), opt[i].val2 = read();
if(s[1] == '2') opt[i].id = -2, opt[i].val1 = read(), opt[i].val2 = read();
if(s[1] == '3') opt[i].id = -3, opt[i].val1 = read();
}
if(s[0] == 'F') {
if(s[1] == '1') opt[i].id = 1, opt[i].val1 = read();
if(s[1] == '2') opt[i].id = 2, opt[i].val1 = read();
if(s[1] == '3') opt[i].id = 3;
}
}
rep(i, 1, q)
if(!opt[i].id) {
int u = opt[i].val1, v = opt[i].val2, fu = find(u), fv = find(v);
if(fu ^ fv) {
fa[fu] = fv;
nxt[tail[fv]] = fu; tail[fv] = tail[fu];
}
}
rep(i, 1, n)
if(find(i) == i)
for(int j = i; j; j = nxt[j]){
dfn[j] = ++cnt;
unid[cnt] = j;
}
SGMT_tree :: build(1, 1, n);
rep(i, 1, n) fa[i] = tail[i] = i, nxt[i] = 0, size[i] = 1;
rep(i, 1, q) {
if(opt[i].id == 0) {
int u = opt[i].val1, v = opt[i].val2, fu = find(u), fv = find(v);
if(fu ^ fv) {
fa[fu] = fv;
nxt[tail[fv]] = fu; tail[fv] = tail[fu];
size[fv] += size[fu];
}
}
if(opt[i].id == -1) {
SGMT_tree :: modify(1, 1, n, dfn[opt[i].val1], dfn[opt[i].val1], opt[i].val2);
}
if(opt[i].id == -2) {
int u = find(opt[i].val1);
SGMT_tree :: modify(1, 1, n, dfn[u], dfn[u] + size[u] - 1, opt[i].val2);
}
if(opt[i].id == -3) SGMT_tree :: modify(1, 1, n, 1, n, opt[i].val1);
if(opt[i].id == 1) printf("%d
", SGMT_tree :: query(1, 1, n, dfn[opt[i].val1], dfn[opt[i].val1]));
if(opt[i].id == 2) {
int u = find(opt[i].val1);
printf("%d
", SGMT_tree :: query(1, 1, n, dfn[u], dfn[u] + size[u] - 1));
}
if(opt[i].id == 3) printf("%d
", SGMT_tree :: query(1, 1, n, 1, n));
}
#ifdef Qrsikno
cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
return 0;
}