【LG-P3920/WC2014】 紫荆花之恋

· · 题解

Solution

在此提供一种可能相对其他解法较为好写的做法。

一

首先考虑一棵如下图的树，其中 rtlr_0=6,\ rtlr_1=5。

发现此时这棵树不考虑根节点只有两条链，而左右链的末尾分别是 rtlr_0 和 rtlr_1。

同时，按照套路，我们将 dist(i,j) \leq r_i+r_j 化为 dist(i, l)-r_i\leq r_j-dist(j,l)，其中 l 为 i 和 j 的最近公共祖先。

对于上图，我们只用维护 4 棵平衡树（使用平衡树因为我们是在维护在某一集合内比某数要大的值的个数）就可以把答案求出，具体实现如下：


inline void add(int u, int v, int w){
    e[++cnt] = (edge){v, hd[u], w}, hd[u] = cnt;
    e[++cnt] = (edge){u, hd[v], w}, hd[v] = cnt;
}

inline void rotate(int &x, int k){
    int y = t[x].ch[k];
    t[x].ch[k] = t[y].ch[!k], t[y].ch[!k] = x;
    t[y].s = t[x].s, 
    t[x].s = t[t[x].ch[1]].s + t[t[x].ch[0]].s + 1;
    x = y;
}

inline void insrt(int &x, int v){
    if(!x){
        x = ++tot;
        t[x].s = 1, t[x].a = v;
        return;
    }
    bool k = (v >= t[x].a);
    insrt(t[x].ch[k], v), t[x].s += 1;
    if(t[x].s * 0.8 < t[t[x].ch[k]].s) 
        rotate(x, k);
}

inline int query(int x, int v){
    if(!x) return 0;
    if(v <= t[x].a) 
        return query(t[x].ch[0], v) + t[t[x].ch[1]].s + 1;
    else return query(t[x].ch[1], v);
}

int main(){
    rd(), n = rd(), rd(), rd(), val[1] = rd();
    rtlr[0] = rtlr[1] = 1;
    printf("0\n");
    insrt(rt1[0], val[1]), insrt(rt1[1], val[1]);//rt1/2[0]维护左边的分支 
    insrt(rt2[0], val[1]), insrt(rt2[1], val[1]);//rt1/2[1]维护右边的分支 
    for(i = 2; i <= n; ++i){
        f[i] = rd() ^ ans % mod, j = rd(), val[i] = rd();
        if(f[i] != rtlr[1] and f[i] != rtlr[0]) break;//如果此时不满足只有两条链的形态，就 break 掉 
        add(i, f[i], j);
        dis[i] = dis[f[i]] + j;//dis[i] 为 i 到根节点的距离 
        fx = (f[i] == rtlr[1])/*看 i 在左右哪条链上*/, rtlr[fx] = i;
        ans += query(rt1[fx], dis[i] - val[i]) + query(rt2[!fx], dis[i] - val[i]); 
        if(dis[i] <= val[1] + val[i]) ans -= 1;//减去重复计算的 
        insrt(rt1[fx], dis[i] + val[i]), insrt(rt2[fx], val[i] - dis[i]);//rt1和rt2分别插入不同的值，辅助求解答案 
        printf("%lld\n", ans); 
    } 
}

二

然后我们再来考虑当树的形态不满足上面的要求时，如下图：

1. 求解答案

面对这种情况，我们对于每个点要维护两棵平衡树：

一棵用于记录以当前节点 i 为根的树内每个子节点 j 的 r_j-dist(j, fa_i) 的值，这棵平衡树的根的编号记为 ms_i；

一棵用于记录当前节点 i，它其中一个儿子 j，j 子树内的所有子节点 k 的 r_k-dist(k,i) 的值，记为 gs_i（注意 gs_i 中并没有记录 i 的直接儿子 j 的信息）。

对于每个节点，我们再去维护它分别到每一个深度的祖先的距离，对于第 k 层的祖先，节点 i 到它的距离记为 adis_{k,i}。

然后我们试着去求一下对于新增的一个节点 i，最终答案是多少。

过程如下：

    for(k = dep[f[i]], l = f[i], o = i; l; k--, o = l, l = f[l])
        u = adis[k][i] - val[i],
        ans += query(gs[l], u) - query(ms[o], u);

我们从下往上去遍历每一个祖先，对于每一个祖先，我们利用刚刚对每个节点维护的两棵平衡树进行求解答案。

2. 添加新节点

然后我们就考虑如何把这个节点加入这棵树内。

首先，肯定是按照刚刚求答案那样，从下往上去遍历祖先，对于每一个祖先，我们分别在它的两棵平衡树内插入新节点的信息即可。

但是如果单单只是这样，树的深度就可能会无止境地增加，这绝不是我们想要的。

所以这时候就要请出替罪羊树了！ 我们用替罪羊树的思路，在从下往上遍历祖先的同时，去检查每棵子树的大小有没有超过其父亲子树大小的 0.88 倍。

如果有，就把它记录下来，然后就对它进行重构。

重构一棵树的步骤：

  1. “拍扁”这棵树，然后选出一个大小刚刚好超过或等于总节点数一半的节点，把它当做新根。

  2. 对于这个新根，我们去建立它的新平衡树，然后对它的每一个儿子，重复第 1 和 2 步。

然后这道题就结束了，复杂度可过。

虽然口胡起来并不复杂，但是代码实现的时候还是需要注意很多细节的。

Code

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 5;
const int mod = 1000000000;

inline int rd(){
    int x = 1, s = 0;
    char ch = getchar();
    while(ch < '0' or ch > '9'){
        if(ch == '-') x = -1;
        ch = getchar();
    }
    while(ch >= '0' and ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * x;
}

struct tree{
    int s, a;
    int ch[2];
}t[maxn * 200];
bool fx;
int rt1[2], rt2[2], rtlr[2];
int n, m, i, j, k, l, o, u, v;
int val[maxn], f[maxn];
int cnt, hd[maxn];
struct edge{
    int to, nxt, w;
}e[maxn << 1];
int tsiz[maxn], siz[maxn], in[maxn], id[maxn];
int gs[maxn], ms[maxn];
int dep[maxn], dis[maxn], adis[100][maxn];
int pre[maxn], he, ta, que[maxn];
int tot;
ll ans;

inline void add(int u, int v, int w){
    e[++cnt] = (edge){v, hd[u], w}, hd[u] = cnt;
    e[++cnt] = (edge){u, hd[v], w}, hd[v] = cnt;
}

inline void rotate(int &x, int k){
    int y = t[x].ch[k];
    t[x].ch[k] = t[y].ch[!k], t[y].ch[!k] = x;
    t[y].s = t[x].s, 
    t[x].s = t[t[x].ch[1]].s + t[t[x].ch[0]].s + 1;
    x = y;
}

inline void insrt(int &x, int v){
    if(!x){
        x = ++tot;
        t[x].s = 1, t[x].a = v;
        return;
    }
    bool k = (v >= t[x].a);
    insrt(t[x].ch[k], v), t[x].s += 1;
    if(t[x].s * 0.8 < t[t[x].ch[k]].s) 
        rotate(x, k);
}

inline int query(int x, int v){
    if(!x) return 0;
    if(v <= t[x].a) 
        return query(t[x].ch[0], v) + t[t[x].ch[1]].s + 1;
    else return query(t[x].ch[1], v);
}

inline int fndrt(int x, int tdep, int tdis, int fa){
    int i, j, k;
    he = ta = 0;
    que[ta++] = x, dis[x] = tdis;
    pre[x] = 0;
    while(he != ta){
        i = que[he++];
        dep[i] = tdep + 1, tsiz[i] = 1;
        for(j = hd[i]; j; j = e[j].nxt){
            k = e[j].to;
            if(k != pre[i] and dep[k] >= tdep)
                que[ta++] = k, pre[k] = i, 
                dis[k] = dis[i] + e[j].w;
        }
        if(tdep) adis[tdep - 1][i] = dis[i];
    }
    for(i = ta - 1; i >= 0; --i){
        k = pre[que[i]];
        tsiz[k] += tsiz[que[i]];
        if(tsiz[que[i]] * 2 >= ta) break;
    }
    j = que[i], f[j] = fa, siz[j] = ta, dep[j] = tdep;
    if(tdep) in[j] = x, id[j] = tdis;
    else in[j] = id[j] = 0;
    return j;
}

inline void build(int x){
    int i, j, k, l, o;
    adis[dep[x]][x] = gs[x] = 0;
    insrt(gs[x], val[x]);
    for(i = hd[x], j = e[i].to; i; i = e[i].nxt, j = e[i].to){
        if(dep[j] < dep[x]) continue;
        k = fndrt(j, dep[x] + 1, e[i].w, x);
        ms[k] = 0;
        for(l = 0; l < siz[k]; ++l){
            o = que[l];
            insrt(gs[x], val[o] - dis[o]);
            insrt(ms[k], val[o] - dis[o]);
        }
        build(k);
    }
}

inline void calc(int i){
    add(i, f[i], j);
    dep[i] = dep[f[i]] + 1, siz[i] = 1, 
    in[i] = i, id[i] = j;
    insrt(gs[i], val[i]);
    for(k = 0; k < dep[i]; ++k) 
        adis[k][i] = adis[k][f[i]] + j;
    for(k = dep[f[i]], l = f[i], o = i; l; k--, o = l, l = f[l])
        u = adis[k][i] - val[i],
        ans += query(gs[l], u) - query(ms[o], u);
    printf("%lld\n", ans);
    for(k = dep[f[i]], v = 0, l = f[i], o = i; l; k--, o = l, l = f[l]){
        u = val[i] - adis[k][i];
        insrt(gs[l], u), insrt(ms[o], u);
        siz[l] += 1;
        if(siz[l] * 0.88 < siz[o]) v = l;
    }
    if(v){
        if(dep[v]) u = fndrt(in[v], dep[v], id[v], f[v]);
        else u = fndrt(1, 0, 0, 0);
        ms[u] = ms[v], ms[v] = 0;
        build(u); 
    }
}

int main(){
    rd(), n = rd(), rd(), rd(), val[1] = rd();
    rtlr[0] = rtlr[1] = 1;
    printf("0\n");
    insrt(rt1[0], val[1]), insrt(rt1[1], val[1]);
    insrt(rt2[0], val[1]), insrt(rt2[1], val[1]);
    for(i = 2; i <= n; ++i){
        f[i] = rd() ^ ans % mod, j = rd(), val[i] = rd();
        if(f[i] != rtlr[1] and f[i] != rtlr[0]) break;
        add(i, f[i], j);
        dis[i] = dis[f[i]] + j;
        fx = (f[i] == rtlr[1]), rtlr[fx] = i;
        ans += query(rt1[fx], dis[i] - val[i]) + query(rt2[!fx], dis[i] - val[i]); 
        if(dis[i] <= val[1] + val[i]) ans -= 1;
        insrt(rt1[fx], dis[i] + val[i]), insrt(rt2[fx], val[i] - dis[i]);
        printf("%lld\n", ans); 
    } 
    if(i > n) return 0;
    for(k = 1; k <= tot; ++k)   
        t[k].ch[0] = t[k].ch[1] = 0;
    tot = 0, memset(dis, 0, sizeof dis);
    k = fndrt(1, 0, 0, 0), build(k);
    for(calc(i), i += 1; i <= n; ++i)
        f[i] = rd() ^ ans % mod, j = rd(), val[i] = rd(), calc(i);
    return 0;
}

感谢阅读。

辛苦管理员审核，若有问题烦请指出。