# 一无所|知的小|J f

### 题解 P3273 【[SCOI2011]棘手的操作】

posted on 2019-03-27 15:58:01 | under 题解 |

## Leafy Tree 题解！

### 我们就直接来顺一下思路吧qwq

inline int find(int x) {
while(fa[x])
x = fa[x];
return x;
}

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#define maxn 18000010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, z, k;
int a[maxn], b[maxn], siz[maxn], fa[maxn], son[maxn][2], dis[maxn], maxx[maxn], tag[maxn];
int cnt, res;
int root; //leafy2的根
const double alp = 1.0-sqrt(2)/2, lim = (1.0-2*alp)/(1.0-alp), spl = alp/(1.0-alp);
int ex = 0;
char ch;

inline void in(re int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x=x*f;
}

void out(int a){
if(a<0){
a*=-1;
putchar('-');
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}

inline int ifr(int x) {
return x == son[fa[x]][1];
}

inline int New() {
++cnt;
return cnt;
}

inline int NNew(int x) {
++cnt;
maxx[cnt] = x;
siz[cnt] = 1;
return cnt;
}

inline void Clear(int x) {
siz[x] = fa[x] = son[x][0] = son[x][1] = tag[x] = 0;
maxx[x] = -99999;
}

inline void push_up(int x) {
if(son[x][0]) {
siz[x] = siz[son[x][0]] + siz[son[x][1]];
maxx[x] = max(maxx[son[x][0]], maxx[son[x][1]]);
}
}

inline void push_down(int x) {
if(son[x][0] && tag[x]) {
maxx[son[x][0]] += tag[x];
maxx[son[x][1]] += tag[x];
tag[son[x][0]] += tag[x];
tag[son[x][1]] += tag[x];
tag[x] = 0;
}
}

inline void rotate(int x) {
int f = fa[x], ff = fa[f], pd1 = ifr(x), pd2 = ifr(f), t = son[x][pd1^1];
son[ff][pd2] = x;
son[x][pd1^1] = f;
son[f][pd1] = t;
fa[t] = f;
fa[f] = x;
fa[x] = ff;
push_up(f);
push_up(x);
if(f == root)
root = x;
}

inline void maintain(int x) {
int pd;
if(son[x][0]) {
if(siz[son[x][0]] < siz[x]*alp)
pd = 1;
else
if(siz[son[x][1]] < siz[x]*alp)
pd = 0;
else
return;
if(siz[son[son[x][pd]][pd^1]] >= siz[son[x][pd]]*lim)
rotate(son[son[x][pd]][pd^1]);
rotate(son[x][pd]);
}
}

void ins(int now, int x) {
if(!root) {
root = NNew(x);
return;
}
if(siz[now] == 1) {
fa[son[now][0] = NNew(x)] = now;
fa[son[now][1] = NNew(maxx[now])] = now;
if(x > maxx[now])
swap(son[now][0], son[now][1]);
}
else  ins(son[now][x > maxx[son[now][0]]], x);
push_up(now);
maintain(now);
}

void del(int now, int x) {
int sid = x > maxx[son[now][0]], t;
if(siz[son[now][sid]] == 1) {
Clear(son[now][sid]);
fa[t = son[now][sid^1]] = fa[now];
son[fa[now]][ifr(now)] = t;
Clear(now);
if(now == root)
root = t;
now = t;
}
else  del(son[now][sid], x);
push_up(now);
maintain(now);
}

inline int merge(int u, int v) {
if(!u || !v)  return u+v;
push_down(u), push_down(v);
if(siz[u] >= siz[v] && siz[v] >= siz[u]*spl || siz[v] >= siz[u] && siz[u] >= siz[v]*spl) {
int cur = New();
fa[son[cur][0] = u] = cur;
fa[son[cur][1] = v] = cur;
push_up(cur);
return cur;
}
if(siz[u] >= siz[v]) {
push_down(u);
int ls = son[u][0], rs = son[u][1];
Clear(u);
if(siz[ls] >= (siz[ls]+siz[rs]+siz[v])*alp)
return merge(ls, merge(rs, v));
push_down(rs);
int lrs = son[rs][0], rrs = son[rs][1];
Clear(rs);
return merge(merge(ls, lrs), merge(rrs, v));
}
else {
push_down(v);
int ls = son[v][0], rs = son[v][1];
Clear(v);
if(siz[rs] >= (siz[ls]+siz[rs]+siz[u])*alp)
return merge(merge(u, ls), rs);
push_down(ls);
int lls = son[ls][0], rls = son[ls][1];
Clear(ls);
return merge(merge(u, lls), merge(rls, rs));
}
}

inline int find(int x) {
while(fa[x])
x = fa[x];
return x;
}

inline int mark_up(int x) { //标记并找根
while(fa[x])
dis[x] = 1, x = fa[x];
return x;
}

void clear_down(int x, int k) { //顺着标记往下找并清除标记, 修改数据
if(siz[x] == 1) {
dis[x] = 0;
maxx[x] += k;
return;
}
push_down(x);
if(dis[son[x][0]])
clear_down(son[x][0], k);
if(dis[son[x][1]])
clear_down(son[x][1], k);
push_up(x);
dis[x] = 0;
}

int main() {
in(n);
cnt = n;
ins(root, -0x7fffffff);
FOR(i, 1, n) {
in(maxx[i]),
siz[i] = 1;
ins(root, maxx[i]);
}
in(m);
FOR(i, 1, m) {
ch = getchar();
while(ch != 'U' && ch != 'A' && ch != 'F')
ch = getchar();
if(ch == 'U') {
in(x), in(y);
int fx = find(x), fy = find(y);
if(fx != fy) {
del(root, maxx[fx]);
del(root, maxx[fy]);
ins(root, maxx[merge(fx, fy)]);
}
//这个地方需要维护一下leafy2
}
if(ch == 'A') {
ch = getchar();
if(ch == '1') {
in(x), in(k);
int xx = mark_up(x);
del(root, maxx[xx]); //leafy2
//沿着标记找到x且下推标记, 最终修改并上推
//维护leafy2;
clear_down(xx, k);
ins(root, maxx[xx]); //新旧交替
}
if(ch == '2') {
in(x), in(k);
int xx = find(x);
tag[xx] += k;

del(root, maxx[xx]);
maxx[xx] += k;
ins(root, maxx[xx]);
}
if(ch == '3') {
in(k);
ex += k;
}
}
if(ch == 'F') {
ch = getchar();
if(ch == '1') {
in(x);
int xx = mark_up(x);

clear_down(xx, 0);  //沿着标记找到x且下推标记;
out(maxx[x]+ex), putchar(10);
}
if(ch == '2') {
in(x);
int xx = find(x);
out(maxx[xx]+ex), putchar(10);
//注意与上面的不同
}
if(ch == '3') {
out(maxx[root]+ex), putchar(10);
}
}
}
}