AT_abc389_f [ABC389F] Rated Range 题解

bluewindde · 2025-01-18 22:17:21 · 题解

难评 \green{525}\red{(2)}。

把询问的点插入一维空间，每一场比赛将在区间 [l, r] 之间的点向正方向平移一个单位。

注意到 K-D Tree 是一棵树，所以平移操作可以在树上打标记完成。操作结束后下放所有标记即可得到答案。

分析时间复杂度，因为只移动一个单位，所以平移操作不改变点的相对顺序，也就不破坏 K-D Tree 的结构，时间复杂度为 O(q \log q)。

以下是场后进行了微调的代码。

#include <algorithm>
#include <iostream>

using namespace std;

const int QMAX = 3e5 + 5;

int n, q;
struct node {
    int x, w;
    friend inline bool operator<(const node &x, const node &y) {
        return x.x < y.x;
    }
} a[QMAX];
int b[QMAX];

struct {
    int l, r;
} seg[QMAX];
int ans[QMAX];

int rt;
struct {
    int ls, rs, l, r, dx;
} kd[QMAX];
static inline void move(int p, int dx) {
    if (!p)
        return;
    a[p].x += dx;
    kd[p].l += dx;
    kd[p].r += dx;
    kd[p].dx += dx;
}
static inline void pushdown(int p) {
    move(kd[p].ls, kd[p].dx);
    move(kd[p].rs, kd[p].dx);
    kd[p].dx = 0;
}
static inline void maintain(int p) {
    kd[p].l = kd[p].r = a[p].x;
    kd[p].dx = 0;
    if (kd[p].ls) {
        kd[p].l = min(kd[p].l, kd[kd[p].ls].l);
        kd[p].r = max(kd[p].r, kd[kd[p].ls].r);
    }
    if (kd[p].rs) {
        kd[p].l = min(kd[p].l, kd[kd[p].rs].l);
        kd[p].r = max(kd[p].r, kd[kd[p].rs].r);
    }
}
static inline int build(int l, int r) {
    if (l > r)
        return 0;
    int mid = (l + r) >> 1;
    nth_element(a + l, a + mid, a + r + 1);
    kd[mid].ls = build(l, mid - 1);
    kd[mid].rs = build(mid + 1, r);
    maintain(mid);
    return mid;
}
static inline void dfs(int p) {
    if (!p)
        return;
    pushdown(p);
    dfs(kd[p].ls);
    dfs(kd[p].rs);
}
static inline void rebuild() { // 事实上不需要重构
    dfs(rt);
    rt = build(1, q);
}
static inline void move(int l, int r, int p) {
    if (!p || r < kd[p].l || l > kd[p].r)
        return;
    if (l <= kd[p].l && kd[p].r <= r)
        return move(p, 1);
    pushdown(p);
    if (l <= a[p].x && a[p].x <= r)
        ++a[p].x;
    move(l, r, kd[p].ls);
    move(l, r, kd[p].rs);
    maintain(p);
}

static inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> seg[i].l >> seg[i].r;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int x;
        cin >> x;
        a[i] = {x, i};
    }
    rt = build(1, q);
    for (int i = 1; i <= n; ++i)
        move(seg[i].l, seg[i].r, rt);
    dfs(rt);
    for (int i = 1; i <= q; ++i)
        ans[a[i].w] = a[i].x;
    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    cout.flush();
    return 0;
}