题解 P3273 【[SCOI2011]棘手的操作】
Juan_feng
2019-03-27 15:58:01
## Leafy Tree 题解！
~~几天不写数据结构浑身难受.jpg~~
嗯呐蒟蒻就不废话了， 直接进入正题qwq
### 我们就直接来顺一下思路吧qwq
**操作1**： **加边**： 找到两个根直接把根merge起来
**操作2**：**将x节点的权值增加k** ： 先找到根， 同时对经过的路径做标记， 这样找到跟之后， 我们再顺着做好的标记往下推add标记， 推回到x节点之后， 修改x的值， 然后pushup。
**操作3**： **x所在连通块整体+k**： 找到x的根， 打add标记
**操作4**： **全局加k**： 我们发现全局加只要用一个变量ss维护一下就可以了， 用不着修改我们的树。
**操作5**： **输出一个节点的值**： 找到根， 同时对经过的路径做标记， 然后下推add标记， 最后输出x节点的值+ss。
**操作6**： **输出x连通块的最大值**： 找到根， 直接输出根所维护的最大值+ss。
**操作7**： **输出全局最大值**： 这里我们发现， 必须单独维护一下这个最大值了， 当然还是可以用Leafy Tree。 我们一开始把所有点的权值都插进这棵Leafy 然后每次合并或者修改的时候就在这棵Leafy上瞎搞就行了。
这里要说明一下， Leafy不像左偏树， ta的树高是可以保障的， 所以找根的时候可以直接像下面这样：
```
inline int find(int x) {
while(fa[x])
x = fa[x];
return x;
}
```
而且我们发现一开始所保存的节点的序号始终不会发生改变， 这样我们第x个节点的ID肯定是x， 查询的时候就很容易啦。
另外还要注意一点: 开始的时候别忘了加上哨兵， 不然会RE3#， 且蒟蒻的代码没有手写内存池， 不过既然不写也能过就懒得加上去了qaqaq
那么这道题也就愉快的解决啦>_<！
代码如下：
```
#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);
}
}
}
}
```