一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

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

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

Leafy Tree 题解!

几天不写数据结构浑身难受.jpg

嗯呐蒟蒻就不废话了, 直接进入正题qwq

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

操作1加边: 找到两个根直接把根merge起来

操作2将x节点的权值增加k : 先找到根, 同时对经过的路径做标记, 这样找到跟之后, 我们再顺着做好的标记往下推add标记, 推回到x节点之后, 修改x的值, 然后pushup。

操作3x所在连通块整体+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);
            }
        }
    }
}