平衡树合并

我们知道，FHQ 平衡树具有 merge 函数，可以在期望 \(O(\log n)\) 的时间内将两棵平衡树的中序遍历直接拼接起来，也就是常说的“无交合并”。

有时，平衡树的中序遍历具有确定的顺序（值域、下标），合并两棵平衡树的结果不一定是中序遍历的拼接，可能出现交叉的情况，即“带交合并”。

带交合并

我们提供一种高效的带交合并：

int merge(int x, int y) {
    if(!x || !y) return x | y;
    int p, q;
    split(x, mn[y], p, q);
    return merge0(p, merge(y, q));
}

时间复杂度分析

对于一棵平衡树 \(T\)，记 \(x_i\) 表示排名第 \(i\) 小的元素的值。定义其势能函数 \(\Phi(T)\) 为

\[ \Phi(T)=\sum_{i=1}^{sz[T]-1}\log_2(x_{i+1}-x_i) \]

结论：

• 平衡树带交合并的均摊时间复杂度不超过 \(O\big(q\log V\log n+\sum \Phi(T_i)\log n\big)=O\big((n+q)\log n\log V\big)\)；
• split 操作不增加势能；

证明：

考虑两棵平衡树 \(T_1\) 和 \(T_2\)，记它们合并之后的结果为 \(T_3\)。

对于 \(T_1\) 和 \(T_2\) 的重合部分（\(x\in T_1\text{ and } x\in T_2\)），容易发现每次 merge 都会使不同的数字数量减少。每遇到一个重复数字，都会花费 \(O(\log n)\) 的时间复杂度进行处理（split 和 merge0 各调用一次）。均摊时间复杂度 \(O(n\log n)\)。

现在我们去除了 \(T_1\) 和 \(T_2\) 的交集部分。考虑合并前后的势能变化：

[   a1   ]                        [  a2  ]                          [ a3 ]
          <- d1 ->        <- d2 ->        <- d3 ->          <- d4 ->         ...
                  [  b1  ]                        [   b2   ]

图中的线段表示 \(T_1\) 或 \(T_2\) 独有的一段值域区间，不要求区间内部的元素连续。

\[ \begin{align*} \Delta\Phi=&\ \Phi(T_1)+\Phi(T_2)-\Phi(T_1\cup T_2)\\ =&\ \log(d_1+b_1+d_2)+\log(d_2+a_2+d_3)\cdots +\log(d_{k-1}+a_{\lceil\frac{k}{2} \rceil}+d_k)\\ &-\log(d_1)-\log(d_2)-\log(d_3)\cdots-\log(d_k)\\ \ge&\ \log(d_1+d_2)+\log(d_2+d_3)\cdots+\log(d_{k-1}+d_k)\\ &-\log(d_1)-\log(d_2)-\log(d_3)\cdots-\log(d_k)\\ \end{align*} \]

由 \(\log x\) 的凸性：

\[ \log(\frac{a+b}{2})\ge \frac{\log(a)+\log(b)}{2} \]

即

\[ \log(a+b)\ge 1+\frac 12\big(\log(a)+\log(b)\big) \]

因此

\[ \begin{align*} \Delta\Phi\ge&\ \log(d_1+d_2)+\log(d_2+d_3)\cdots+\log(d_{k-1}+d_k)\\ &-\log(d_1)-\log(d_2)-\log(d_3)\cdots-\log(d_k)\\ \ge&\ k-\log(d_1+d_k)\\ =&\ k-O(\log V) \end{align*} \]

初始势能与势能增量的和为 \(O\big((n+q)\log V\big)\)。

由于，merge 会调用 \(k\) 次 split 和 merge0，每次的时间复杂度都是 \(O(\log n)\)。因此每产生 \(O(k\log n)\) 的时间复杂度都会至少降低 \(k\) 的势能。总时间复杂度为 \(O\big((n+q)\log n\log V\big)\)。

split 操作显然不增加势能，因此这种合并方式可以适用于反复合并的情况。

参考：bicsi 的 CF Blog

P3224 [HNOI2012] 永无乡

使用并查集和 FHQ 维护即可。

代码

#include<iostream>
using namespace std;
const int N = 1E5 + 10;

int n, m, q;
int val[N], pri[N], sz[N], mn[N], chd[N][2];

int rt[N];
namespace unf {
    int fa[N];
    void init() {
        for(int i = 0; i < N; i++) {
            rt[i] = fa[i] = i;
        }
    }
    int find(int x){
        if(fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
}

inline void push_up(int p){
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
    mn[p] = min(val[p], min(mn[chd[p][0]], mn[chd[p][1]]));
}

void split(int cur, int k, int &x, int &y){
    if(cur == 0){
        x = y = 0;
        return;
    }
    if(val[cur] <= k){
        x = cur;
        split(chd[cur][1], k, chd[x][1], y);
    } else{
        y = cur;
        split(chd[cur][0], k, x, chd[y][0]);
    }
    push_up(cur);
}

int merge0(int x, int y) {
    if(!x || !y) return x | y;
    if(pri[x] > pri[y]) {
        chd[x][1] = merge0(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        chd[y][0] = merge0(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

int merge(int x, int y) {
    if(!x || !y) return x | y;
    int p, q;
    split(x, mn[y], p, q);
    return merge0(p, merge(y, q));
}

int queryKth(int cur, int k){
    if(k <= sz[chd[cur][0]]) return queryKth(chd[cur][0], k);
    if(k == sz[chd[cur][0]] + 1) return cur;
    return queryKth(chd[cur][1], k - sz[chd[cur][0]] - 1);
}

void dfs(int x, int &y){
    if(x == 0 || y == 0) return;
    dfs(chd[x][0], y);
    dfs(chd[x][1], y);
    chd[x][0] = chd[x][1] = 0;
    int a, b;
    split(y, val[x], a, b);
    y = merge(merge(a, x), b);
}

int main(){

    srand(time(NULL));
    unf::init();

    mn[0] = 0x3f3f3f3f;

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> val[i];
        pri[i] = rand();
        sz[i] = 1;
        mn[i] = val[i];
    }
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        if(unf::find(u) == unf::find(v)) continue;
        int nrt = merge(rt[unf::find(u)], rt[unf::find(v)]);
        unf::merge(u, v);
        rt[unf::find(u)] = nrt;
    }
    cin >> q;
    while(q--){
        char op;
        int u, v, x, y;
        cin >> op;
        if(op == 'B'){
            cin >> u >> v;
            if(unf::find(u) == unf::find(v)) continue;
            int nrt = merge(rt[unf::find(u)], rt[unf::find(v)]);
            unf::merge(u, v);
            rt[unf::find(u)] = nrt;
        } else{
            cin >> x >> y;
            if(sz[rt[unf::find(x)]] < y) cout << -1 << endl;
            else cout << queryKth(rt[unf::find(x)], y) << endl;
        }
    }

    return 0;
}

插入标记回收算法

P10284 [USACO24OPEN] Splitting Haybales P

题意

给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，每个下标都对应一个分段函数：

\[ f_i(x)= \begin{cases} x+a_i,\ x\le 0\\ x-a_i,\ x> 0 \end{cases} \]

有 \(m\) 次询问，每次询问给定 \([l,r]\) 和初始值 \(v\)，你需要求出：依次遍历 \(i\in [l,r]\)，执行 \(v\leftarrow f_i(v)\) 得到的最终结果。

\(n,m,a_i\le 2\times 10^5,\ v\le 10^9\)

先将所有询问离线，然后从左往右依次扫描下标 \(i\)。对于所有区间左端点 \(l=i\) 的询问 \((l,r,v)\)，向 FHQ 中插入一个值为 \(v\) 的节点表示这个询问。

然后使用 split，move_tag 和 megre 对整棵平衡树进行 \(f_i\) 的变换：\(T\leftarrow f_i(T)\)。

split(rt, 0, x, y);
move_tag(x, a[i]);
move_tag(y, -a[i]);
rt = merge(x, y);

然后，对于所有区间右端点 \(r=i\) 的询问 \((l,r,v)\)，取出 \(l\) 位置插入的节点，查询其现在的值作为答案。

由于需要反复 split 和 merge，我们可以使用上面提到的均摊 \(O(n\log^2 n)\) 的带交合并。时间复杂度为 \(O(n\log^2 n)\)。

代码

#include<iostream>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
const int N = 2e5 + 10;

int n, t;
int a[N], ans[N];
int b[N], pt[N];

vector<int> bg[N], ed[N];

namespace fhq {
    mt19937 rng(clock());
    int mn[2 * N], val[2 * N], tag[2 * N], chd[2 * N][2], pri[2 * N], fa[2 * N], rt, nn;
    inline int addNode(int v) {
        val[++nn] = v;
        mn[nn] = v;
        pri[nn] = rng();
        return nn;
    }
    inline void push_up(int p) {
        mn[p] = val[p];
        if(chd[p][0]) { fa[chd[p][0]] = p; mn[p] = min(mn[p], mn[chd[p][0]]); }
        if(chd[p][1]) { fa[chd[p][1]] = p; mn[p] = min(mn[p], mn[chd[p][1]]); }
    }
    inline void move_tag(int p, int tg) {
        if(!p) return;
        tag[p] += tg;
        val[p] += tg;
        mn[p] += tg;
    } 
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(chd[p][0], tag[p]);
        move_tag(chd[p][1], tag[p]);
        tag[p] = 0;
    }
    void split(int p, int v, int &x, int &y) {
        if(p == 0) {
            x = y = 0;
            return; 
        }
        push_down(p);
        if(val[p] <= v) {
            x = p;
            split(chd[x][1], v, chd[x][1], y);
        } else {
            y = p;
            split(chd[y][0], v, x, chd[y][0]);
        }
        push_up(p);
    }
    int merge0(int x, int y) {
        if(!x || !y) return x | y;
        if(pri[x] > pri[y]) {
            push_down(x);
            chd[x][1] = merge0(chd[x][1], y);
            push_up(x);
            return x;
        } else {
            push_down(y);
            chd[y][0] = merge0(x, chd[y][0]);
            push_up(y);
            return y;
        }
    }
    int merge(int x, int y) {
        if(!x || !y) return x | y;
        int p, q;
        split(x, mn[y], p, q);
        return merge0(p, merge(y, q));
    }
    // push_down_to_rt
    void pushrt(int p) {
        if(p != rt) pushrt(fa[p]);
        push_down(p);
    } 
}

using namespace fhq;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    cin >> t;
    for(int i = 1; i <= t; i++) {
        int l, r;
        cin >> l >> r >> b[i];
        bg[l].push_back(i);
        ed[r].push_back(i);
    }

    for(int i = 1; i <= n; i++) {
        for(int j : bg[i]) {
            pt[j] = addNode(b[j]);
            rt = merge(rt, pt[j]);
        } 
        int x, y;
        split(rt, 0, x, y);
        move_tag(x, a[i]);
        move_tag(y, -a[i]);
        rt = merge(x, y);
        for(int j : ed[i] ) {
            pushrt(pt[j]);
            ans[j] = val[pt[j]];
        }
    }

    for(int i = 1; i <= t; i++) {
        cout << ans[i] <<'\n';
    }

    return 0;
}

P8264 [Ynoi Easy Round 2020] TEST_100

题意

给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，每个下标都对应一个分段函数：

\[ \begin{align*} f_i(x)&=|x-a_i|\\&= \begin{cases} x-a_i,\ x>a_i\\ -x+a_i,\ x\le a_i \end{cases} \end{align*} \]

有 \(m\) 次询问，每次询问给定 \([l,r]\) 和初始值 \(v\)，你需要求出：依次遍历 \(i\in [l,r]\)，执行 \(v\leftarrow f_i(v)\) 得到的最终结果。

询问强制在线。

\(n,m,a_i,v\le 10^5\)

由于存在 \(-x\) 的操作，我们需要额外给平衡树维护一个区间翻转、取相反数的 tag。

考虑如何处理强制在线。考虑序列分块，块长为 \(b\)。我们为每个块维护一个 \(tsf[i]\) 数组，表示查询 \((bg[b],ed[b],i)\) 的答案。对于查询，我们将散块暴力模拟，整块使用 \(tsf\) 数组。

考虑平衡块长 \(b\)。查询的时间复杂度显然是 \(O(mb+\frac{nm}{b})\)。对于预处理，由于这里的平衡树结构比较特殊，完整连续地覆盖了整个 \([1,n]\) 的值域，因此不能使用上面的势能分析（势能一直为 \(0\)，会存在过度放缩）。我们发现，每产生一个重叠的元素，就会花费 \(O(\log n)\) 的时间进行一次 split 和 merge，并将不同数字数量减少 \(1\) 个。因此块内时间复杂度不超过 \(O(n\log n)\)。

这样，总复杂度就是 \(O(\frac{n^2\log n}{b}+mb)\)，平衡得 \(b=n\sqrt{\frac{\log n}m}\)，时间复杂度 \(O(n\sqrt{m\log n})\)。由于平衡树的常数比分块查询大很多，因此块长应该调大一点（\(2\) 倍即可）。

代码

#include<iostream>
#include<algorithm>
#include<random>
#include<ctime>
#include<unistd.h>
#include<cassert>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
const int N2 = 5010;
const int V = 1e5;

namespace fhq {
    mt19937 rng(clock());
    int chd[N][2];
    int val[N], mn[N], mx[N], pri[N];
    int tag_mul[N], tag_add[N];
    int rt, nn;
    inline int addNode(int v) {
        ++nn;
        mn[nn] = mx[nn] = val[nn] = v;
        chd[nn][0] = chd[nn][1] = 0;
        pri[nn] = rng();
        tag_add[nn] = 0;
        tag_mul[nn] = 1;
        return nn;
    }
    inline void push_up(int p) {
        mx[p] = mn[p] = val[p];
        if(chd[p][0]) {
            mn[p] = min(mn[p], mn[chd[p][0]]);
            mx[p] = max(mx[p], mx[chd[p][0]]);
        }
        if(chd[p][1]) {
            mn[p] = min(mn[p], mn[chd[p][1]]);
            mx[p] = max(mx[p], mx[chd[p][1]]);
        }
    }
    inline void move_tag_add(int p, int tg) {
        val[p] += tg;
        mn[p] += tg;
        mx[p] += tg;
        tag_add[p] += tg;
    }
    inline void move_tag_mul(int p) {
        swap(mn[p], mx[p]);
        swap(chd[p][0], chd[p][1]);
        mn[p] = -mn[p], mx[p] = -mx[p];
        val[p] = -val[p];
        tag_mul[p] = -tag_mul[p];
        tag_add[p] = -tag_add[p];
    }
    inline void push_down(int p) {
        if(tag_mul[p] != 1) {
            if(chd[p][0]) move_tag_mul(chd[p][0]);
            if(chd[p][1]) move_tag_mul(chd[p][1]);
            tag_mul[p] = 1;
        }
        if(tag_add[p]) {
            if(chd[p][0]) move_tag_add(chd[p][0], tag_add[p]);
            if(chd[p][1]) move_tag_add(chd[p][1], tag_add[p]);
            tag_add[p] = 0;
        }
    }
    void split(int p, int v, int &x, int &y) {
        if(!p) {
            x = y = 0;
            return;
        }
        push_down(p);
        if(val[p] <= v) {
            x = p;
            split(chd[x][1], v, chd[x][1], y);
        } else {
            y = p;
            split(chd[y][0], v, x, chd[y][0]);
        }
        push_up(p);
    }
    int merge0(int x, int y) {
        if(!x || !y) return x | y;
        if(pri[x] > pri[y]) {
            push_down(x);
            chd[x][1] = merge0(chd[x][1], y);
            push_up(x);
            return x;
        } else {
            push_down(y);
            chd[y][0] = merge0(x, chd[y][0]);
            push_up(y);
            return y;
        }
    }
    // 带交合并
    int merge(int x, int y) {
        if(!x || !y) return x | y;
        int p, q;
        split(x, mn[y], p, q);
        return merge0(p, merge(y, q));
    }
    // 对整棵树进行变换
    void transf(int v) {
        int x, y;
        split(rt, v, x, y);
        move_tag_mul(x);
        move_tag_add(x, v);
        move_tag_add(y, -v);
        rt = merge(x, y);
    }
    // 输出到数组
    void output(int p, int *arr) {
        if(!p) return;
        push_down(p);
        arr[p - 1] = val[p];
        output(chd[p][0], arr);
        output(chd[p][1], arr);
    }
    // void print(int p) {
    //     if(!p) return;
    //     push_down(p);
    //     print(chd[p][0]);
    //     cout << val[p] << ' ';
    //     print(chd[p][1]);
    // }
}

int n, m;

namespace backup {
    int chd[N][2];
    int val[N], mn[N], mx[N], pri[N];
    int rt, nn;
    void save() {
        memcpy(val, fhq::val, sizeof(val));
        memcpy(chd, fhq::chd, sizeof(chd));
        memcpy(mn, fhq::mn, sizeof(mn));
        memcpy(mx, fhq::mx, sizeof(mx));
        memcpy(pri, fhq::pri, sizeof(pri));
        rt = fhq::rt, nn = fhq::nn;
    }
    void load() {
        memcpy(fhq::val, val, sizeof(val));
        memcpy(fhq::chd, chd, sizeof(chd));
        memcpy(fhq::mn, mn, sizeof(mn));
        memcpy(fhq::mx, mx, sizeof(mx));
        memcpy(fhq::pri, pri, sizeof(pri));
        for(int i = 1; i <= n; i++) fhq::tag_add[i] = 0;
        for(int i = 1; i <= n; i++) fhq::tag_mul[i] = 1;
        fhq::nn = nn, fhq::rt = rt;
    }
}
int a[N];

int blen, bcnt;
int blo[N];

int bg[N2], ed[N2];
int tsf[N2][N];

int f(int i, int x) { return abs(x - a[i]); }

int query(int v, int l, int r) {
    if(blo[l] == blo[r]) {
        for(int i = l; i <= r; i++) v = f(i, v);
        return v;
    }
    if(l != bg[blo[l]]) {
        for(int i = l; i <= ed[blo[l]]; i++) v = f(i, v);
        l = ed[blo[l]] + 1;
    }
    int br = blo[r] - (r != ed[blo[r]]);
    for(int i = blo[l]; i <= br; i++) v = tsf[i][v];
    if(r != ed[blo[r]]) {
        for(int i = bg[blo[r]]; i <= r; i++) v = f(i, v);
    }
    return v;
}

using namespace fhq;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    blen = sqrt((long long)n * n * __lg(n) / m) * 2;
    bcnt = (n + blen - 1) / blen;
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;

    for(int i = 1; i <= bcnt; i++) bg[i] = (i - 1) * blen + 1;
    for(int i = 1; i <= bcnt; i++) ed[i] = i * blen;
    ed[bcnt] = n;

    for(int i = 0; i <= V; i++) rt = merge0(rt, addNode(i));

    backup::save();

    for(int b = 1; b <= bcnt; b++) {
        backup::load();
        for(int i = bg[b]; i <= ed[b]; i++) {
            transf(a[i]);
        }
        output(rt, tsf[b]);
    }

    int lstans = 0;
    for(int i = 1; i <= m; i++) {
        int l, r, v;
        cin >> l >> r >> v;
        l ^= lstans;
        r ^= lstans;
        v ^= lstans;
        cout << (lstans = query(v, l, r)) << '\n';
    }

    return 0;
}