洛谷P6138 [IOI2012] 骑马比武竞赛

洛谷传送门

分析

首先可以将骑士比赛这件事视为将一段区间缩为一个点。那么最后剩下的一段区间中每个点一定是有一个区间浓缩而来。展开这个区间，展开后的区间中的每个点也是由一个区间浓缩而来。这样逐步展开，会得到原本的有 \(n\) 个元素的数组。注意，虽然迟到的还没有加入，但是各区间的包含情况是不变的。所以我们将区间的包含情况建成一棵树，且称为区间树。

接下来我们考虑一个骑士什么时候会输。显然，将这个骑士代表的叶子不断往上跳，第一次跳到一个含有比他大的能力值的区间时，他就输了。为了求出迟到的放在每个位置能赢几场，我们可以对区间树进行 dfs，同时维护一个栈，栈中存当前点的所有祖先。走到叶子，就代表我们要把迟到的放在这个叶子对应的位置。那接下来就要求他往上跳多少会挂掉。

由于我们已经维护了一个存当前点所有祖先的栈，我们就可以在栈里面二分，二分出他输掉的位置。为此，我们还需要对输入的 \(n - 1\) 个元素的数组建 ST 表，以支持查区间最值。注意，由于原本的数组中并没有迟到的，所以此时查的区间会发生变化，具体细节可以看代码。

最后还剩下建区间树。发现题目实际上要支持一个区间删除，单点查值。使用平衡树维护即可。连边可以暴力。

总复杂度一个 \(\log\)。

代码

#include <iostream>
#include <random>
#define lowbit(x) ((x) & -(x))
using namespace std;
mt19937 mtrand(3225 * 2532 + 21060621);
int n, c, X;
int L[300005], R[300005];
int head[300005], nxt[600005], to[600005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int rt;
struct node {
    int l, r, sz, val;
    unsigned int prio;
} T[300005];
int tn[300005], tncnt;
int ncnt;
int New(int val) {
    T[++ncnt] = (node) { 0, 0, 1, val, mtrand() };
    return ncnt;
}
void pushup(int x) { T[x].sz = T[T[x].l].sz + T[T[x].r].sz + 1; }
void Split(int x, int& l, int& r, int k) {
    if (!x) 
        return l = r = 0, void();
    if (k >= T[T[x].l].sz + 1) {
        l = x;
        Split(T[x].r, T[l].r, r, k - T[T[x].l].sz - 1);
    } else {
        r = x;
        Split(T[x].l, l, T[r].l, k);
    }
    pushup(x);
}
int Merge(int x, int y) {
    if (!x || !y) 
        return x | y;
    if (T[x].prio > T[y].prio) {
        T[y].l = Merge(x, T[y].l);
        pushup(y);
        return y;
    } else {
        T[x].r = Merge(T[x].r, y);
        pushup(x);
        return x;
    }
}
int Kth(int x, int k) {
    if (k <= T[T[x].l].sz) 
        return Kth(T[x].l, k);
    else if (k > T[T[x].l].sz + 1) 
        return Kth(T[x].r, k - 1 - T[T[x].l].sz);
    return T[x].val;
}
void Adde(int x, int f) {
    add(f, tn[T[x].val]);
    if (T[x].l) 
        Adde(T[x].l, f);
    if (T[x].r) 
        Adde(T[x].r, f);
}
int mx[24][100005];
int lg2[300005];
int Query(int l, int r) {
    int k = lg2[r - l + 1];
    return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}
int stk[300005], sz;
int ans = -1, pos = 2147483647;
bool chk(int x, int p) {
    x = stk[x];
    int l = L[x], r = R[x];
        --r;
    return Query(l, r) < X;
}
void dfs(int x) {
    if (!head[x]) {
        int l = 1, r = sz, mid, ans = sz + 1;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (chk(mid, x)) 
                ans = mid, r = mid - 1;
            else 
                l = mid + 1;
        }
        ans = sz - ans + 1;
        if (ans > ::ans) 
            ::ans = ans, pos = x;
        if (ans == ::ans) 
            pos = min(pos, x);
        return;
    }
    stk[++sz] = x;
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        dfs(v);
    }
    --sz;
}
void dfs1(int x) {
    if (T[x].l) 
        dfs1(T[x].l);
    dfs(tn[T[x].val]);
    if (T[x].r) 
        dfs1(T[x].r);
}
int main() {
    cin >> n >> c >> X;
    for (int i = 1; i < n; i++) cin >> mx[0][i];
    lg2[0] = -1;
    for (int i = 1; i <= n; i++) rt = Merge(rt, New(tn[i] = i)), lg2[i] = lg2[i - 1] + (lowbit(i) == i), L[i] = R[i] = i;
    tncnt = n;
    while (c--) {
        int l, r;
        cin >> l >> r;
        ++l, ++r;
        int tl = Kth(rt, l), tr = Kth(rt, r);
        int a, b, c, d;
        Split(rt, a, b, l - 1);
        Split(b, b, c, r - l + 1);
        ++tncnt;
        L[tncnt] = L[tn[tl]], R[tncnt] = R[tn[tr]];
        Adde(b, tncnt);
        Split(b, b, d, 1);
        rt = Merge(a, Merge(b, c));
        tn[tl] = tncnt;
    }
    for (int i = 1; (1 << i) <= n - 1; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n - 1; j++) 
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
    }
    dfs1(rt);
    cout << pos - 1 << "\n";
    return 0;
}

另外好像有简单无数倍的线段树做法，但是我不会。