自动搬运

查看原文

来自洛谷，原作者为

	Swirl 你可以祈祷，但神不会倾听。

搬运于2025-08-24 22:19:10，当前版本为作者最后更新于2025-02-17 23:05:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

理解了最高赞题解做法做出的这道黑题，特此留念。

SGT（替罪羊树） + SGT（线段树）

首先，直接递归比较两个「数」是非常麻烦的，考虑用类似哈希的思想将每一个「数」对应成一个实数（不一定是整数），接下来的比较就变得简单了。

但是问题是该如何对每个「数」赋一个值呢？

我们先把所有的「数」放到一棵平衡树上。

对于以 $u$ 为根的子树，传入一个区间 $\left [ L, R \right ]$。

先将 $u$ 的权值赋为 $\frac{L + R}{2}$，接着分别往左右儿子递归传入 $\left [ L, \frac{L + R}{2} \right ]$、$\left [ \frac{L + R}{2}, R \right ]$（根节点的传参随便设置一个就行，代码中用的是 $\left [ 0, 1 \right ]$）。

可以证明此时的赋值一定满足平衡树的性质。

显然，这里的赋值不能用整数（因为精度太低），考虑用浮点数。

但是如果不用特殊的方法维护树高退化成一条链后浮点数的精度也不够。

如果用 Splay 等旋转类平衡树，就无法快速维护赋值的结果，其复杂度就会大大提升。

考虑用替罪羊树解决问题。

我们正好可以在重构的时候重新为整棵平衡树赋值，此时既保证了树高平衡又保证了复杂度平衡。

最后用线段树维护最大值编号即可。

具体实现的注意事项或技巧：

• 可以开一个 $pos$ 数组，用来存储数组 $a$ 中的下标对应到平衡树中的位置，在线段树中方便维护。
• 存储 $(a_l, a_r)$ 时可以分别记录 $a_l$ 和 $a_r$ 在平衡树里的位置（因为以前一定插入过），然后比较会更方便。
• $\alpha$ 不要写成 int 类型了……
• 建议不要用 pair，会莫名其妙 WA。
• 结点插进来就不要删了，因为后面的计算可能会用到。

#include <bits/stdc++.h>
#define int long long
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
using namespace std;

inline void cmax(int& x, int c) {
    x = max(x, c);
}
inline void cmin(int& x, int c) {
    x = min(x, c);
}

int _test_ = 1;
const int N = 5e5 + 5;
const double alpha = 0.75;
int n, m, rt, pos[N];
double V[N];  // 赋上的值

struct node {  // 存储 (L, R)
    int l, r;
    bool operator<(const node& x) const {
        return V[l] < V[x.l] ||
               (V[l] == V[x.l] && V[r] < V[x.r]);  // 比较规则题面
    }
    bool operator==(const node& x) const { return l == x.l && r == x.r; }
};

struct scape_goat {
    int tot, siz[N];      // 目前总结点数，子树大小
    node val[N];          // 值
    int son[N][2];        // 儿子
    void pushup(int u) {  // 上传
        siz[u] = siz[son[u][0]] + siz[son[u][1]] + 1;
    }
    int nwnode(node v) {  // 新建节点
        tot++;
        siz[tot] = 1;
        val[tot] = v;
        return tot;
    }
    bool ck_reb(int u) {  // 是否重构
        return alpha * siz[u] > (double)max(siz[son[u][0]], siz[son[u][1]]);
    }
    void re_dfs(vector<int>& p, int u) {  // 拍扁
        if (!u)
            return;
        re_dfs(p, son[u][0]);
        p.push_back(u);
        re_dfs(p, son[u][1]);
    }
    int re_bui(vector<int>& p, int l, int r, double L, double R) {  // 提起来
        if (l > r)
            return 0;
        int mid = (l + r) >> 1;
        double Mid = (L + R) / 2.0;
        V[p[mid]] = Mid;
        son[p[mid]][0] = re_bui(p, l, mid - 1, L, Mid);
        son[p[mid]][1] = re_bui(p, mid + 1, r, Mid, R);
        pushup(p[mid]);
        return p[mid];
    }
    void rebuild(int& u, double L, double R) {  // 重构函数
        vector<int> p;
        re_dfs(p, u);
        u = re_bui(p, 0, p.size() - 1, L, R);
    }
    int ins(int& u, node v, double L, double R) {  // 插入一个 v，取 [L, R] 赋值
        double Mid = (L + R) / 2.0;
        if (!u) {
            u = nwnode(v);
            V[u] = Mid;
            return u;
        }
        if (val[u] == v)
            return u;
        siz[u]++;
        int ret = (v < val[u]) ? ins(son[u][0], v, L, Mid)
                               : ins(son[u][1], v, Mid, R);
        if (!ck_reb(u))
            rebuild(u, L, R);
        return ret;
    }
} sgt;

struct segment_tree {
#define ls (id << 1)
#define rs (id << 1 | 1)
    int mx[N];  // 最大值下标
    void change(int id, int lft, int rht, int x) {
        if (lft == rht) {
            mx[id] = x;
            return;
        }
        int mid = (lft + rht) >> 1;
        if (x <= mid)
            change(ls, lft, mid, x);
        else
            change(rs, mid + 1, rht, x);
        mx[id] = (V[pos[mx[ls]]] >= V[pos[mx[rs]]]) ? mx[ls] : mx[rs];  // 上传
    }
    int query(int id, int lft, int rht, int l, int r) {
        if (l <= lft && rht <= r)
            return mx[id];
        int mid = (lft + rht) >> 1;
        if (r <= mid)
            return query(ls, lft, mid, l, r);
        if (l > mid)
            return query(rs, mid + 1, rht, l, r);
        int L = query(ls, lft, mid, l, mid);
        int R = query(rs, mid + 1, rht, mid + 1, r);
        return (V[pos[L]] >= V[pos[R]]) ? L : R;
    }
} seg;

void solve() {
    cin >> n >> m;
    sgt.ins(rt, node{0, 0}, 0.0, 1.0);  // 插入最原始的 0
    for (int i = 1; i <= n; i++)        // 赋初值
        pos[i] = 1;
    for (int i = 1; i <= n; i++)
        seg.change(1, 1, n, i);
    while (m--) {
        char c;
        int l, r;
        cin >> c >> l >> r;
        if (c == 'Q') {
            cout << seg.query(1, 1, n, l, r) << "\n";
        } else {
            int x;
            cin >> x;
            pos[x] = sgt.ins(rt, node{pos[l], pos[r]}, 0.0, 1.0);  // 插入
            seg.change(1, 1, n, x);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}