自动搬运

查看原文

来自洛谷，原作者为

	船酱魔王 如花美眷，似水流年

搬运于2025-08-24 23:00:30，当前版本为作者最后更新于2024-09-28 17:56:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Changelog

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

题意回顾

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

• 在队尾增加一个小团队，给定人数和类型；
• 在队伍中间踢出一个小团队；
• $k$ 个人进入游乐场，从队头开始，若该小团队可以全部进入就全部进入，否则若可以拆分就进入剩余名额个人。请输出进游乐场的人员所属小团队及该小团队进入人数。

操作次数不超过 $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;
}