P10711 题解

· · 题解

Changelog

修改了码风和影响理解的变量名，抱歉影响管理员时间导致重新审核。

题意回顾

请你维护三种对于一个队列的操作：

操作次数不超过 2 \times 10^5 。

分析

可以发现一个小团队只会被完整地离开队列一次，每次操作最多导致一个小团队部分离开队列。因此小团队的人员变动次数是线性量级的。考虑设计关于此的势能复杂度算法。

我们需要快速找到下一个需要人员变动的位置，数据范围较小考虑分块，考虑如果一个段内都没有人员变动的条件：这个段内没有还在队列里的可拆分小团队，并且这个段内的所有小团队的人数都严格大于剩余名额数。显然这两个数值都可以被修改时快速维护。

对于一个段，如果被跳过，则带来 O(1) 的时间复杂度；如果不被跳过，会至少出现一次人员变动。对于一次修改，耗时是 O(\sqrt{n}) 。

所以，时间复杂度为 O(n\sqrt n) 。

AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define whr pair<int, int>
using namespace std;
const int N = 2e5 + 5;
const int S = 448;
int q, n;
int a[N];
int b[N];
int lmq1[N];// min of all
int lmq2[N];// sum of free
ll remb;
vector<whr> lyh;
inline void eat(int i) {
    if(!a[i]) return;
    if(remb >= a[i]) remb -= a[i], lyh.push_back((whr){i, a[i]}), a[i] = 0;
    else if(b[i]) a[i] -= remb, lyh.push_back((whr){i, remb}), remb = 0;
}
inline void abcde(int x) {
    int blo = x / S * S;
    int bd = min(n, blo + S - 1);
    lmq1[x / S] = N, lmq2[x / S] = 0;
    for(int i = blo; i <= bd; i++) {
        lmq1[x / S] = min(lmq1[x / S], ((a[i] == 0) ? N : a[i])), lmq2[x / S] += b[i] && a[i];
    }
}
int main() {
    scanf("%d", &q);
    int op, tp;
    ll x;
    for(int qi = 1; qi <= q; qi++) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%lld%d", &x, &tp);
            a[++n] = x, b[n] = tp;
            abcde(n);
        } else if(op == 2) {
            scanf("%lld", &x);
            a[x] = 0;
            abcde(x);
        } else if(op == 3) {
            scanf("%lld", &x);
            remb = x;
            for(int blo = 0; blo <= n / S; blo++) {
                if(!lmq2[blo] && (lmq1[blo] > remb || lmq1[blo] == N)) continue;
                int lf, rt;
                lf = blo * S;
                rt = min(n, lf + S - 1);
                for(int i = lf; i <= rt; i++) {
                    eat(i);
                    if(!remb) break;
                }
                abcde(blo * S);
                if(!remb) break;
            }
            printf("%d\n", (int)lyh.size());
            for(int i = 0; i < lyh.size(); i++) printf("%d %d\n", lyh[i].first, lyh[i].second);
            lyh.clear();
        } else puts("dthkxy AK IOI");
    }
    return 0;
}