【WC2014】紫荆花之恋（替罪羊重构点分树 & 平衡树）

Description

若带点权、边权的树上一对 \((u, v)\) 为 friend，那么需要满足 \(\text{dist}(u, v) \le r_u + r_v\)，其中 \(r_x\) 为点 \(x\) 的权，\(\text{dist}(u, v)\) 表示 \(u, v\) 的树上距离，即 \(u, v\) 间的简单路径上的边权和。

一开始树为空，之后有 \(n\) 次加点操作，每次各处该点需要连接的结点、点权以及边权。对于每次加点之后得到的树，你需要输出当前树上 friends 的对数。强制在线。

Hint

\(1\le n\le 10^5, 1\le \text{边权}\le 10^4, 1\le \text{点权}\le 10^9\)。

Solution

这里的加点操作非常难搞，因此不妨试着先离线。如果可以离线，我们可以先把树建出来，一开始 \(\forall i\in[1, n],r_i\leftarrow -\infty\)，然后一个个将点权修改。这就不难用 动态点分治 维护。

考虑将原来的式子进行变形：\(\text{dist}(u, v) \le r_u + r_v \quad\longrightarrow\quad r_v - \text{dist}(u, v) \le -r_u\)，然后就是对于每个 \(u\) 数一数满足条件的 \(v\) 的个数。

这比较显然可以用 平衡树 维护，不过在跑点分树的过程中，如果直接将答案加上点分子树的贡献，会与其祖先的答案算重。于是再对点分树父亲维护一颗平衡树用作容斥。这样一次修改是 \(O(\log^2 n)\) 的，而答案显然可以在修改时计算影响。

于是现在我们有 \(O(n\log^2 n)\) 的离线算法了。

考虑在线化改造这个算法。如果不做改动，每次插入建一次点分树的话复杂度会变成 \(O(n^2\log^2 n)\)；而如果插入节点后干脆不对点分树做改动的话，众所周知仍然会被卡，不该也不行。

于是尝试均摊一下这两部分。如果我们选择根号重构，那么树高只能控制在 \(O(\sqrt{n})\)，这样复杂度为 \(O(n^{1.5}\log n)\)，并不理想。

但如果选择替罪羊式重构的话，我们的树高就能被控制在 \(O(\log n)\)。所谓替罪羊式重构，就是对于一个结点如果它的某一子树的大小占据的整颗子树的 \(\alpha(\approx 0.8)\) 倍，那么就部分重构这颗子树。

这样的复杂度是均摊 \(O(n\log^2 n)\) 的，并且做到了在线。

写起来真的非常复杂，而且需要注意常数。优化技巧：

使用较快的平衡树，不要用 Splay 或 FHQ-Treap；
计算树上距离不需要再写一个 LCA，直接记录每个点到祖先的距离即可。因为一个点的祖先数不超过 \(O(\log n)\)；
重构选择深度最浅的重构点进行重构；
Fast IO method。

Code

附上 Luogu 上卡到 Page 1（2020.10.14）的代码：

/*

 * Author : _Wallace_

 * Source : https://www.cnblogs.com/-Wallace-/

 * Problem : WC2014 紫荆花之恋

 */

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int N = 1e5 + 5;

const int mod = 1e9;

const int LogN = 18;

struct IO {

    static const int S=1<<24;

    char buf[S],*p1,*p2;int st[105],Top;

    ~IO(){clear();}

    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}

    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}

    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

    IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n');return *this;}

    template<typename T> IO&operator >> (T&x){

        x=0;bool f=0;char ch=gc();

        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}

        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();

        f?x=-x:0;return *this;

    }

    IO&operator << (const char c){pc(c);return *this;}

    template<typename T> IO&operator << (T x){

        if(x<0) pc('-'),x=-x;

        do{st[++st[0]]=x%10,x/=10;}while(x);

        while(st[0]) pc('0'+st[st[0]--]);

        return *this;

    }

} fin, fout;

#define alpha 0.7

namespace bst_nodes { // 奇怪的平衡树实现：不平衡就旋转，这样跑的很快

    struct Node {

        int ch[2], val, cnt, siz;

        inline Node() { }

        inline Node(int l, int r, int v, int c, int s) :

            val(v), cnt(c), siz(s) { ch[0] = l, ch[1] = r; }

    } t[N << 6];

    int total = 0;

    int rec[N << 6], top = 0;

    inline void create(int& x, int v) {

        x = top ? rec[top--] : ++total;

        t[x] = Node(0, 0, v, 1, 1);

    }

    inline void pushup(int& x) {

        t[x].siz = t[x].cnt + t[t[x].ch[0]].siz + t[t[x].ch[1]].siz;

    }

    inline void rotate(int& x, int d) {

        int y = t[x].ch[d];

        if (t[x].siz * alpha > t[y].siz) return;

        t[x].ch[d] = t[y].ch[!d];

        t[y].ch[!d] = x, pushup(x), pushup(x = y);

    }

    void insert(int& x, int v) {

        if (!x) return create(x, v), void();

        ++t[x].siz;

        if (v == t[x].val) return ++t[x].cnt, void();

        int d = v > t[x].val;

        insert(t[x].ch[d], v), rotate(x, d);

    }

    int count(int x, int v) {

        if (!x) return 0;

        if (t[x].val <= v) return t[t[x].ch[0]].siz + t[x].cnt + count(t[x].ch[1], v);

        else return count(t[x].ch[0], v);

    }

    void recycle(int& x) {

        if (!x) return;

        recycle(t[x].ch[0]), recycle(t[x].ch[1]);

        rec[++top] = x, x = 0;

    }

}

struct bst {

    int root;

    bst() : root(0) { }

    inline void insert(int v) { bst_nodes::insert(root, v); }

    inline void clear() { bst_nodes::recycle(root); }

    inline int count(int v) { return bst_nodes::count(root, v); }

};

int n, Q, R[N];

long long ans = 0ll;

struct Edge {

    int to, len;

    Edge(int t, int l) : to(t), len(l) { }

}; vector<Edge> adj[N];

struct {

    int fa[N], cnt[N], dep[N];

    long long anc[N][LogN << 2];

    bst t[N][2];

    bool vis[N];

    int siz[N], maxp[N], ctr;

    inline long long dist(int x, int a) {

        return anc[x][dep[a]];

    }

    int getSize(int x, int f) {

        siz[x] = 1;

        for (auto y : adj[x]) if (y.to != f && !vis[y.to])

            siz[x] += getSize(y.to, x);

        return siz[x];

    }

    void getCentr(int x, int f, int t) {

        maxp[x] = 0;

        for (auto y : adj[x]) if (y.to != f && !vis[y.to])

            getCentr(y.to, x, t), maxp[x] = max(maxp[x], siz[y.to]);

        maxp[x] = max(maxp[x], t - siz[x]);

        if (maxp[ctr] > maxp[x]) ctr = x;

    }

    void getBst(int s, int x, int f, long long d) {

        t[s][0].insert(d - R[x]);

        if (fa[s]) t[s][1].insert(dist(x, fa[s]) - R[x]);

        for (auto y : adj[x]) if (y.to != f && !vis[y.to])

            getBst(s, y.to, x, d + y.len);

    }

    void getDist(int s, int x, int f, long long d) {

        anc[x][dep[s]] = d;

        for (auto y : adj[x]) if (y.to != f && !vis[y.to])

            getDist(s, y.to, x, d + y.len);

    }

    int rebuild(int x, int f, int d) {

        maxp[ctr = 0] = N;

        getCentr(x, 0, getSize(x, 0));

        int s = ctr;

        vis[s] = 1, fa[s] = f, dep[s] = d, cnt[s] = 1;

        t[s][0].clear(), t[s][1].clear(); getBst(s, s, 0, 0);

        getDist(s, s, 0, 0);

        for (auto y : adj[s]) if (!vis[y.to])

            cnt[s] += cnt[rebuild(y.to, s, d + 1)];

        return vis[s] = 0, s;

    }

    inline long long update(int i, int f, int w) {

        fa[i] = f, dep[i] = dep[f] + 1;

        t[i][0].insert(-R[i]);

        for (int j = 1; j <= dep[f]; j++)

            anc[i][j] = anc[f][j] + w;

        if (i == 1) return 0ll;

        adj[f].emplace_back(i, w);

        adj[i].emplace_back(f, w);

        int target = 0;

        for (int x = i, y = fa[x]; y; y = fa[x = y]) {

            long long dis = R[i] - dist(i, y);

            ans += t[y][0].count(dis) - t[x][1].count(dis);

            t[y][0].insert(-dis), t[x][1].insert(-dis);

            if (++cnt[y] * alpha < cnt[x]) target = y;

        }

        if (target) {

            for (int x = fa[target]; x; x = fa[x]) vis[x] = 1;

            rebuild(target, fa[target], dep[target]);

            for (int x = fa[target]; x; x = fa[x]) vis[x] = 0;

        }

        return ans;

    }

} vdct;

#undef alpha

signed main() {

    fin >> n, fin >> n;

    for (int i = 1, f, w; i <= n; i++) {

        fin >> f >> w >> R[i], f ^= ans % mod;

        fout << vdct.update(i, f, w) << '\n';

    }

}

巴特西

【WC2014】紫荆花之恋（替罪羊重构点分树 & 平衡树）

Description

Hint

Solution

Code

最新文章

热门文章