自动搬运

查看原文

来自洛谷，原作者为

	Crosser 开始厌倦 深海的光 停滞的海浪

搬运于2025-08-24 22:49:53，当前版本为作者最后更新于2023-08-28 14:16:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这个和 另一个普及模拟赛的题 差不多。

我们考虑类似的进行操作，但是这个题多出来了三个更复杂的部分：

• 这是个队列，删除从头删而非从尾删。
• 有最大值操作。
• 有查询第 $x$ 个元素操作。

我们不难逐一解决。

首先对于第一个，我们不会真的删掉，而是通过一个变量 $d$ 记录删掉了多少个，那么如果查询第 $i$ 个元素，真正下标的就是 $d+i$。

对于第二个，我们使用 std::multiset 维护即可。注意到算最大值仍然只有右端点有用。考虑删除操作最多只会删除 $q$ 次，所以暴力找就可以了，复杂度依然不会爆掉。

对于第三个，结合上面算出来的 $d$，使用二分即可。

于是所有操作均在 $\mathcal O(\log q)$ 或 $\mathcal O(1)$ 时间内解决。

int a[200005], s[200005], n;
multiset<int> ms;

void push(int w)
{ 
    a[++n] = w;
    s[n] = s[n - 1] + w;
    ms.insert(w);
}
signed main()
{
    int res = 0, id = 1;
    int q = read();
    q = read();
    while (q--)
    {
        int op = read();
        if (op == 1)
        {
            int x = read();
            push(x);
        }
        if (op == 2)
        {
            int y = read();
            res += y;
            while(s[id] <= res && id <= n) {
                ms.erase(ms.find(a[id]));
                id++;
            }
        }
        if (op == 3)
        {
            int z = read() + res;
            int pos = lower_bound(s + 1, s + n + 1, z) - s - 1;
            cout << z - s[pos] << endl;
        }
        if(op == 4)
        {
            cout << *ms.rbegin() << endl;
        }
    }
    return 0;
}