自动搬运

查看原文

来自洛谷，原作者为

	NobodyThere 刻は流れて、そしていつか詩となる。

搬运于2025-08-24 23:08:05，当前版本为作者最后更新于2025-01-08 16:51:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

是的，我只给我的队伍贡献了 E 题，可见我严重拖累了整支队伍（

试试堆成一列会怎么样。打表观察或者稍微想一下，不难发现：

• 当 $c$ 为奇数时，最终坐标是一段连续以 $x$ 为中心的区间。
• 当 $c$ 为偶数时，最终坐标是一段“几乎连续”的以 $x$ 为中心的区间，其中缺失的恰好为 $x$。

猜想：如果积木的初始位置“足够连续”，那么它们的最终坐标会构成一段“几乎连续”的区间，并且有至多一个坐标的空缺。我们用三元组 $(l,r,p)$ 刻画空缺坐标为 $p$ 的区间 $[l,r]$。（方便起见，若元素间没有空缺，不妨视为空缺在最右边，如 $[1,2,4,5]$ 视为 $(1,5,3)$，而 $[1,2,3,4]$ 视为 $(1,5,5)$）

先考虑如何求一个“足够连续”的段的最终形态：注意到坐标总和 $s=\sum x_i$ 在操作过程中是不变的，因此只要 $s$ 与积木个数 $c$ 固定，$(l,r,p)$ 就是固定的。只需从 $c$ 的奇偶性以及 $\left\lfloor\dfrac sc\right\rfloor, s\bmod c$ 的值考虑即可求出 $(l,r,p)$，具体公式不再赘述。（如果对此有疑惑，可以自行尝试打表找规律，或者参考下面给出的代码）

那么如何知道一个段是否“足够连续”呢？考虑一开始将每一列视作一个单独的连续段，对这些连续段分别求出预期的 $(l,r,p)$，如果对应的区间都不交，那么显然各自为不同的连续段；否则，有交的连续段应合并，视为同一连续段。直接维护一个当前所有连续段的栈，从左到右检查合并即可求出最终形态。

猜想成立，即一个连续段最终构成“几乎连续”的区间的原因如下：

• 首先，如果一个段已经达成了“几乎连续”，那么最终它也是“几乎连续”的。

• 其次，当两个连续段发生干涉，即这两个连续段各有至少一块积木相遇（垒到同一个位置）时，我们总可以认为两个连续段是“几乎连续”的区间，其中左边有至多一个“不活跃”的断点（取决于合并方向；“活跃”的断点是指与当前操作相邻的断点），而右边没有“不活跃”的断点；于是这个处于交界处的“活跃”断点就会吞噬左边“不活跃”的断点（如果有的话）。于是新的连续段在最终时刻也是“几乎连续”的。

于是做法的正确性也得到了保障。复杂度线性。

附上本题主要代码：

int m, q;
int X[N], C[N], K[N];

 // getres 用于求出三元组 (l,r,p)；t 是坐标总和 s，且保证在 [0,c) 的范围内；c 是积木总个数
inline std::tuple<int, int, int> getres(int t, int c) {
    int l, r, p;
    if(c & 1) {
        l = -(c / 2), r = l + c, p = r - t;
    } else {
        if(t < c / 2) l = -(c / 2), r = l + c, p = -t;
        else l = -(c / 2) + 1, r = l + c, p = c + 1 - t;
    }
    return std::make_tuple(l, r, p);
}
struct node {
    int l, r, p, c;
    ll s;
    node() {}
    node(int _c, ll _s) : c(_c), s(_s) {
        int dt = s / c, t = s % c;
        std::tie(l, r, p) = getres(t, c);
        l += dt, r += dt, p += dt;
    }
    node(int _l, int _r, int _p, int _c, ll _s) : l(_l), r(_r), p(_p), c(_c), s(_s) {}
} stk[N];
node operator + (node x, node y) {
    return node(x.c + y.c, x.s + y.s);
}
int tot;
int main() {
    read(m);
    for(int i = 1; i <= m; i++)
        read(X[i], C[i]);
    read(q);
    for(int i = 1; i <= q; i++)
        read(K[i]);
    for(int i = 1; i <= m; i++) {
        auto t = node(C[i], 1ll * X[i] * C[i]);
        while(tot && stk[tot].r >= t.l) {
            t = stk[tot--] + t;
        }
        stk[++tot] = t;
    }
    int cur = 0;
    for(int i = 1, j = 1; i <= q; i++) {
        while(K[i] - cur > stk[j].c) {
            cur += stk[j++].c;
        }
        int qwq = stk[j].l + K[i] - cur - 1;
        if(qwq >= stk[j].p) ++qwq;
        write(qwq, '\n');
    }
    return 0;
}