P11833 [省选联考 2025] 推箱子

· · 题解

竟然和 ABC 的题重了。。。

先考虑贪心做这个问题。很容易想到，按照 t 排序，依次满足要求。每个箱子直接从当前位置推向 b_i，并把过程中遇到的箱子“挤压”着移动。由于 a,b 均递增，这样做并不会妨害到后续箱子的移动，并能最小化当前时间。

那么看起来只需要写一个：区间推平成等差数列，区间求和。由于挤压的存在，实现起来有一定细节。

考虑维护 c_i=a_i-i，显然 c_i\leq c_{i+1}。可以发现，这时操作就转成了区间推平，查询区间和。例如对箱子 i 操作，从 x 位置走向 y 位置，只需把 j\geq i\land c_j\in [x, y] 的值推平成 y 即可（x>y 同理）。步数显然仍是移动前后对应位置 c_i 之差的绝对值。

若用线段树维护，维护区间和与覆盖标记，同时为了在线段树上二分找到推平区间，需要维护区间最值。时间复杂度 \mathcal O(n\log n)。

不过我们注意到，查询区间与覆盖区间总是相同，因此用 ODT 维护即可，时间复杂度也是 \mathcal O(n\log n)。

代码后续补。

这里有一份能通过官方数据的 ODT 实现：

int testcase, n; ll ans;

struct node {
    int a, b, id; ll t;

    il bool operator < (const node &p) const {
        return t < p.t;
    }

    il void input(int i) {
        read(a, b, t);
        a -= i; b -= i; id = i;
    }
} a[MAXN];

struct ODT {
    struct node {
        int l, r;
        mutable int v;

        il bool operator < (const node &p) const {
            return l < p.l;
        }
    }; set <node> odt;

    il void init() {
        odt.clear(); 
        rep1(i, 1, n) odt.emplace(node{i, i, a[i].a});
    }

    il void change(int i) {
        int id = a[i].id;
        auto it = --odt.upper_bound(node{id, -1, -1});
        auto [l0, r0, v0] = *it;
        if (a[i].a < a[i].b) {
            if (l0 ^ id) {
                odt.erase(it); odt.emplace(node{l0, id - 1, v0});
                it = odt.emplace(node{id, r0, v0}).fst;
            } auto itr = it; ll sum = 0; int rpos = id - 1;
            while (itr != end(odt) && itr -> v < a[i].b) {
                auto [l, r, v] = *itr++;
                sum += ll(r - l + 1) * v; rpos = r;
            } odt.erase(it, itr); odt.emplace(node{id, rpos, a[i].b});
            ans += ll(rpos - id + 1) * a[i].b - sum;
        } else {
            if (r0 ^ id) {
                odt.erase(it); odt.emplace(node{id + 1, r0, v0});
                it = odt.emplace(node{l0, id, v0}).fst;
            } auto itl = it; ll sum = 0; int lpos = id + 1;
            while (itl -> v > a[i].b) {
                auto [l, r, v] = *itl;
                sum += ll(r - l + 1) * v; lpos = l;
                if (itl == begin(odt)) break;
                --itl;
            } odt.erase(--odt.upper_bound(node{lpos, -1, -1}), next(it));
            odt.emplace(node{lpos, id, a[i].b});
            ans += sum - ll(id - lpos + 1) * a[i].b;
        }
    }
} T;

il void solve() {
    read(n); ans = 0;
    rep1(i, 1, n) a[i].input(i);
    T.init(); sort(a + 1, a + 1 + n);
    rep1(i, 1, n) if ((T.change(i), ans) > a[i].t) return puts("No"), void();
    puts("Yes");
}

int main() {
    read(testcase);
    for (int T = read(); T--; ) solve();
    return 0;
}

下面是我的赛时代码，线段树写法。

int testcase, n;

struct node {
    int a, b, id; ll t;

    il bool operator < (const node &p) const {
        return t < p.t;
    }

    il void input(int i) {
        read(a, b, t); id = i;
        a -= i, b -= i;
    }
} a[MAXN];

struct setr {
    #define STZ MAXN << 2
    #define ls(x) x << 1
    #define rs(x) x << 1 | 1
    ll sum[STZ]; int maa[STZ], mii[STZ], tg[STZ];

    il void pushup(int x) {
        sum[x] = sum[ls(x)] + sum[rs(x)];
        maa[x] = max(maa[ls(x)], maa[rs(x)]);
        mii[x] = min(mii[ls(x)], mii[rs(x)]);
    }

    il void change(int x, int k, ll len) {
        tg[x] = maa[x] = mii[x] = k;
        sum[x] = k * len;
    }

    il void pushdown(int x, int l, int r) {
        if (!~tg[x]) return;
        int mid = l + r >> 1;
        change(ls(x), tg[x], mid - l + 1);
        change(rs(x), tg[x], r - mid);
        tg[x] = -1;
    }

    il void upd(int x, int l, int r, int ql, int qr, int k) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) return change(x, k, r - l + 1);
        int mid = l + r >> 1; pushdown(x, l, r);
        upd(ls(x), l, mid, ql, qr, k); upd(rs(x), mid + 1, r, ql, qr, k);
        pushup(x);
    }

    il ll query(int x, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return sum[x];
        int mid = l + r >> 1; pushdown(x, l, r);
        return query(ls(x), l, mid, ql, qr) + query(rs(x), mid + 1, r, ql, qr);
    }

    il void build(int x, int l, int r) {
        tg[x] = -1;
        if (l == r) return sum[x] = maa[x] = mii[x] = a[l].a, void();
        int mid = l + r >> 1;
        build(ls(x), l, mid); build(rs(x), mid + 1, r);
        pushup(x);
    }

    il int query1(int x, int l, int r, int k) {
        if (l == r) return l;
        int mid = l + r >> 1; pushdown(x, l, r);
        if (mii[rs(x)] <= k) return query1(rs(x), mid + 1, r, k);
        return query1(ls(x), l, mid, k);
    }

    il int query2(int x, int l, int r, int k) {
        if (l == r) return l;
        int mid = l + r >> 1; pushdown(x, l, r);
        if (maa[ls(x)] >= k) return query2(ls(x), l, mid, k);
        return query2(rs(x), mid + 1, r, k);
    }
} T;

il void solve() {
    read(n);
    rep1(i, 1, n) a[i].input(i);
    T.build(1, 1, n);
    sort(a + 1, a + 1 + n);
    bll now = 0;
    rep1(i, 1, n) {
        int id = a[i].id;
        if (a[i].a < a[i].b) {
            int pos = T.query1(1, 1, n, a[i].b);
            if ((now += a[i].b * ll(pos - id + 1) - T.query(1, 1, n, id, pos)) > a[i].t) return puts("No"), void();
            T.upd(1, 1, n, id, pos, a[i].b);
        } else {
            int pos = T.query2(1, 1, n, a[i].b);
            if ((now += T.query(1, 1, n, pos, id) - a[i].b * ll(id - pos + 1)) > a[i].t) return puts("No"), void();
            T.upd(1, 1, n, pos, id, a[i].b);
        }
    } puts("Yes");
}

int main() {
    read(testcase);
    for (int Q = read(); Q--; ) solve();
    return 0;
}
/*
维护 a_i - i
abc 原题 
*/