题目链接

题目大意

要求你维护一棵树,支持以下操作

  1. 询问 $(u,v)$ 两点之间的距离
  2. 将 $v$ 的祖先变成它的 $k$ 级祖先
  3. 询问深度为 $d$ 的点中最靠右的点是啥。

每层一开始的位置关系在输入中给出 每次 $2$ 操作的时候默认插入到子节点中的最右边。

题解

学了个叫做维护括号序列的东西。。(不知道是不是叫ETT?)
括号序列就是在这个点入栈和出栈的时候都记录一次,比如样例1的括号序列就是 12344321。我们记第 $i$ 个点入栈的位置和出栈的位置分别为 $in_i,out_i$。括号序列的一些性质:
$(in[u],in[v])$ 中未匹配的括号都是路径上除lca和端点以外的点

这个看起来并不是很好维护 于是我们考虑放缩一下 得到另外一个结论
$(in[u],in[v])$ 中的节点的最小值一定是 $lca$ 的儿子。

那么 $1$ 就很好维护了。我们考虑如何维护操作 $2$:发现在括号序列上实现子树移动是很方便的 子树对应的是一段区间 用Splay维护即可。

$3$ 操作可以记录最大值最小值,直接在splay上二分。
代码还是很长的

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;

std::vector<int> G[MAXN];
int in[MAXN],out[MAXN],dep[MAXN],id[MAXN],ts;
int n;

inline void dfs(int v,int d){
    in[v] = ++ts;id[ts] = v;dep[ts] = d;
    for(auto x:G[v]) dfs(x,d+1);
    out[v] = ++ts;id[ts] = v;dep[ts] = d;
}

int f[MAXN],mn[MAXN],mx[MAXN],tag[MAXN],ch[MAXN][2],sz[MAXN];
#define lc (ch[x][0])
#define rc (ch[x][1])

inline void pushup(int x){
    if(!x) return;
    mn[x] = std::min(dep[x],std::min(mn[lc],mn[rc]));
    mx[x] = std::max(dep[x],std::max(mx[lc],mx[rc]));
    sz[x] = sz[lc]+sz[rc]+1;
}

inline void cover(int x,int d){
    mn[x] += d;mx[x] += d;tag[x] += d;dep[x] += d;
}

inline void pushdown(int x){
    if(tag[x]){
        if(lc) cover(lc,tag[x]);
        if(rc) cover(rc,tag[x]);
        tag[x] = 0;
    }
}

inline void rotate(int x){
    int y = f[x],z = f[y],k = ch[y][1]==x,w = ch[x][!k];
    ch[z][ch[z][1]==y] = x;f[x] = z;
    ch[x][!k] = y;f[y] = x;
    ch[y][k] = w;if(w) f[w] = y;
    pushup(y);pushup(x);
}

int rt;
int st[MAXN];

inline void splay(int x,int v=0){
    int y = x,z;
    st[z = 1] = y;
    while(f[y] != v) st[++z] = y = f[y];
    while(z) pushdown(st[z--]);
    while((y=f[x]) != v){
        if((z=f[y]) != v) rotate((ch[z][1]==y)^(ch[y][1]==x) ? x : y);
        rotate(x);
    }
    if(!v) rt = x;
    pushup(x);
}

inline int getk(int k){
    int x = rt;
    while(true){
        pushdown(x);
        if(k <= sz[lc]) x = lc;
        else if(k == sz[lc]+1) return splay(x),x;
        else k -= sz[lc]+1,x = rc;
    }
}

inline int pre(int x){
    splay(x);x = lc;while(rc) x = rc;return x;
}

inline int suf(int x){
    splay(x);x = rc;while(lc) x = lc;return x;
}

inline int split(int x,int y){
    x = pre(x);y = suf(y);
    splay(x);splay(y,x);return ch[y][0];
}

inline int find(int x,int k){
    pushdown(x);
    if(mn[rc] <= k && k <= mx[rc]) return find(rc,k);
    if(dep[x] == k) return splay(x),x;
    return find(lc,k);
}

inline void build(int f,int &x,int l,int r){
    if(l > r) return;
    x = (l+r)>>1;mn[x] = mx[x] = dep[x];sz[x] = 1;tag[x] = 0;::f[x] = f;
    if(l == r) return;
    build(x,lc,l,x-1);build(x,rc,x+1,r);
    pushup(x);
}

inline void dfs(int x){
    pushdown(x);
    if(lc) dfs(lc);
    printf("(%d,%d)",id[x],dep[x]);
    if(rc) dfs(rc);
    pushup(x);
}

int main(){
    mn[0] = 1e9;int m;scanf("%d%d",&n,&m);
    FOR(i,1,n){
        int k;scanf("%d",&k);
        while(k--) {int x;scanf("%d",&x);G[i].pb(x);}
    }
    dfs(1,1);build(0,rt,1,ts);
    while(m--){
        int opt;scanf("%d",&opt);
        if(opt == 1){
            int u,v;scanf("%d%d",&u,&v);int res = 0;
            splay(in[u]);int rku = sz[ch[in[u]][0]]+1;res += dep[in[u]];//询问单点前一定要splay到根 防止标签未下传
            splay(in[v]);int rkv = sz[ch[in[v]][0]]+1;res += dep[in[v]];
//            DEBUG(res);
            if(rku > rkv) std::swap(u,v);
            int t = split(suf(in[u]),pre(out[v]));res -= 2*(mn[t]-1);// 括号序[in[u],out[v]]保存了除lca外的路径上的点
            printf("%d\n",res);
        }
        if(opt == 2){
            int v,h;scanf("%d%d",&v,&h);
            splay(in[v]);int fa = id[find(ch[in[v]][0],dep[in[v]]-h)];
            int t = split(in[v],out[v]);pushdown(f[t]);ch[f[t]][0] = 0;pushup(f[t]);pushup(f[f[t]]);f[t] = 0;
            cover(t,1-h);int tt = pre(out[fa]);splay(tt);splay(out[fa],tt);
            pushdown(out[fa]);ch[out[fa]][0] = t;f[t] = out[fa];pushup(out[fa]);pushup(tt);
        }
        if(opt == 3){
            int k;scanf("%d",&k);splay(1);++k;
            printf("%d\n",id[find(1,k)]);
        }//dfs(rt);puts("");
    }
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/1023/

转载时须注明出处及本声明

Last modification:April 9th, 2020 at 11:53 pm
如果觉得我的文章对你有用,请随意赞赏