队列

· · 题解

Description

你需要维护一个队列，操作共四种，参数分别如下：

  1. 从队尾依次插入 1,2,3,\cdots,x；
  2. 弹出队头的前 k 个元素；
  3. 查询队列中的第 k 个元素；
  4. 查询队列中所有元素的最大值。

维护队列的同时对于每个操作三和操作四，输出查询的答案。

Solution

对于操作一，由于 \sum x\le2\times10^{14}，所以考虑直接使用 x 代表整个序列插入，时间复杂度 \mathcal{O}(1)。

对于操作二和操作三，首先可以想到遍历整个队列，同时维护一个前缀和 sum 表示目前遍历到第 sum 个元素，当 k\le sum+x 时，输出 k-sum，时间复杂度 \mathcal{O}(n^2)（n 表示操作一的数量，下同），当然还需要一点标记和特判，但这不是重点。

由于我们每次都要取一个前缀和，因此我们可以在进行操作一的同时求一下 x 的前缀和 sum，然后在前缀和上进行二分。维护一个 p 表示一共弹出过 p 个元素。对于操作二便直接更新 p\gets p+k，时间复杂度 \mathcal{O}(1)；而对于操作三我们只需要在前缀和数组中二分出第一个大于等于 p+k 的下标，计为 i，输出 p+k-sum_{i-1}，时间复杂度 \mathcal{O}(\log n)。

对于操作四，很显然可以维护一个关于 x 的单调递减队列（在 x 所代表的序列中 x 一定为整个序列的最大值并且在序列的末尾）。由于操作二的弹出操作，则需要同时对队列中的每一个 x_i，我们要记录下它的 sum_i，当 sum_i\le p 时，则将 x_i 和 sum_i 一并弹出。最后输出队列中的第一个元素，总时间复杂度 \mathcal{O}(n)。

总时间复杂度为 \mathcal{O}(q+m\log n)（m 表示操作三的数量）。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200005;
int q, que[N], front, back, rt, x;
long long id[N], sum[N], p;
int read(){
    int x = 0;
    char a = getchar();
    while(a < '0' || '9' < a) a = getchar();
    while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
    return x;
}
void write(int x){
    if(x > 9) write(x / 10);
    putchar(x % 10 | 48);
}
int main(){
    q = (read(), read());
    for(int i = 1; i <= q; ++ i){
        int x = read();
        if(x == 1){
            x = read();
            sum[rt] = sum[rt ++] + x;
            while(front <= back && que[back] <= x) back --;
            que[++ back] = x;
            id[back] = sum[rt];
        }
        else if(x == 2) p += read();
        else if(x == 3){
            x = read();
            write(p + x - sum[lower_bound(sum + 1, sum + rt, p + x) - sum - 1]), puts("");
        }
        else if(x == 4){
            while(front <= back && id[front] <= p) ++ front;
            write(que[front]), puts("");
        }
    }
    return 0;
}

其实也可以再稍微优化掉一个数组 id，用单调队列直接维护前缀和数组 sum 的下标，这里设为 i，x_i 就是 sum_i-sum_{i-1}。