LG9588 - 队列

Eclipsalad · 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;
}