题解

一组观众必须占据连续空位，所以我们可以把当前空位分成若干个极大的连续空段。一次入座需要做两件事，在每个能容纳这组观众的空段里找出最好的位置，再在这些位置之间按距离优先、左端点次优先进行比较。离开操作则会让相邻空段合并。

座位数可以达到 $10^9$，空段数却只和操作数有关。用空段表示状态后，就不需要逐个维护座位了。

一个空段里应当坐在哪里

先看两端都有观众的内部空段 $[l,r]$，长度记为 $g=r-l+1$。它左右相邻的座位 $l-1,r+1$ 都有人，其他已占座位只会离得更远。

若新组坐在 $[x,x+k-1]$，设左边剩下 $a=x-l$ 个空位，右边剩下 $b=r-(x+k-1)$ 个空位。两边空位数满足 $a+b=g-k$，与原先观众的最小距离为

两个非负整数的和固定为 $g-k$，较小的那个最多是 $\lfloor(g-k)/2\rfloor$。把剩余空位尽量均分到两侧，就能达到这个上界。因此该空段内的最大距离为

还要确定并列时的最左位置。要取得上述距离，两边至少都要留下 $\lfloor(g-k)/2\rfloor$ 个空位。令左边恰好留下这么多，左端点就最小，得到

当 $g-k$ 为奇数时，两个居中的位置都能取得最优距离，公式选择靠左的那个。例如空段为 $[3,8]$、$k=3$ 时，$g-k=3$，应选择 $[4,6]$，而不是同样最优的 $[5,7]$。

端点空段只需要远离一侧的观众。对于左端空段 $[1,r]$，把新组放在 $[1,k]$，距离为 $r-k+1=g-k+1$；对于右端空段 $[l,N]$，放在 $[N-k+1,N]$，距离同样为 $g-k+1$。这里没有除以二的过程。

如果整排座位都是空的，直接按题意选择 $[1,k]$。参考代码用 $N+1$ 作为这个特殊候选的比较值，它只是程序中的哨兵值，不表示题目定义了无人入座时的距离。所有类型的空段都要先检查 $g\ge k$，否则不能容纳新组。

可以先拿到哪些部分分

对于子任务 1，可以开一个长度为 $N$ 的数组记录座位是否有人。一次入座时，先用左右两遍扫描算出每个空座位到最近原有观众的距离，再用长度为 $k$ 的滑动窗口求区间最小值，只考虑全部为空的窗口，依次比较距离和左端点。离开时清空对应区间。一次操作花费 $O(N)$，总时间 $O(Nq)$，空间 $O(N+q)$，可通过 $N,q\le2000$ 的子任务 1，获得 10 分。

掌握空段公式后，还可以直接枚举全部空段。每次入座用常数时间计算一个空段的候选，离开时合并两侧相接的空段。空段数为 $O(q)$，总时间 $O(q^2)$，空间 $O(q)$。在 $q\le3000$ 时，候选计算量至多约为 $9\times10^6$ 次。这种做法能通过子任务 1、2，获得 30 分。

子任务 3 保证组大小始终为同一个 $K$。这样一个空段的最优距离和最左位置都固定，可以直接把这两个量作为优先队列的比较依据。每次取出最优空段，入座后插入剩余空段；离开时仍用按位置排序的结构找到相邻空段，并插入合并结果。给空段分配唯一编号，删除时标记失效，优先队列取堆顶时跳过失效项即可。每次操作只产生常数个空段，每个失效项至多弹出一次，总时间 $O(q\log q)$，空间 $O(q)$。该方法能通过子任务 3，获得这组的 20 分；与前面的枚举做法按输入条件选用，可以拿到 50 分。

子任务 4 只有入座操作，空段只会分裂，不会合并。内部空段可以按长度奇偶分成两个堆，每个堆先按长度从大到小，再按左端点从小到大排序。对于相同奇偶性的长度，每增长 $2$，$d(g,k)$ 恰好增长 $1$，所以每个堆只需考虑堆顶；相同长度选最左的空段。端点空段单独维护，每次比较两个堆顶和至多两个端点候选。取中的内部空段直接弹出，分裂后的内部空段入堆，不需要动态查找邻居来做合并。堆顶放不下当前这组观众时，本次忽略它，但不能丢弃，因为以后可能来更小的组。总时间 $O(q\log q)$，空间 $O(q)$，可通过子任务 4，获得这组的 15 分。

完整做法只检查至多四个候选

当 $k$ 可以变化时，内部空段之间的距离并列关系也可能变化。设当前最长内部空段的长度为 $G$。对本次固定的 $k$，距离 $d(g,k)$ 随 $g$ 单调不减。若 $G<k$，任何内部空段都放不下这组观众。

若 $G\ge k$，所有长度 $g\le G-2$ 的可用内部空段都有

它们不可能成为最优内部候选。只剩下长度为 $G$ 和 $G-1$ 的空段。后者有时能与最长空段取得相同距离，并且可能处于更靠左的位置，所以不能省略。例如 $k=2$ 时，长度 $6$ 和长度 $7$ 的内部空段都能取得距离 $3$。

对于长度相同的空段，公式中的偏移量 $\lfloor(g-k)/2\rfloor$ 相同，空段左端点越小，入座左端点也越小。因此只需分别取长度 $G$、$G-1$ 中最靠左的空段，再与左右端点空段比较。至多四个候选就覆盖了全部可能的答案。

程序维护两份索引。gap 是按空段左端点排序的 map，保存全部极大空段的右端点。它负责查找入座位置所在的空段，以及离开时左右两侧的空段。inside 是按 $(g,l)$ 排序的 set，只保存内部空段的长度和左端点。

从 inside 的末尾取得最大长度 $G$ 后，对 $(G,0)$ 和 $(G-1,0)$ 分别做 lower_bound，便能找到对应长度中最靠左的空段。查找结果的长度必须与目标相等，否则说明这种长度不存在。左右端点空段则从 gap 的第一个、最后一个元素中检查。

一次入座成功后，设原空段为 $[l,r]$，选中的座位为 $[x,x+k-1]$。先从两份索引中删除原空段，再插入非空的 $[l,x-1]$ 和 $[x+k,r]$。按本次操作编号记录入座区间，供后续离开使用。入座失败时不改动状态。

一组占据 $[l,r]$ 的观众离开时，只有紧贴该区间左右两侧的空段可能与它连通。用 gap.lower_bound(l) 的前驱检查是否存在右端点为 $l-1$ 的空段，有就删除并扩展左端点；再查找是否存在左端点为 $r+1$ 的空段，有就删除并扩展右端点。把最终区间插入两份索引即可。两端都有人、只在一侧有空段、两侧都有空段、整排重新变空，都会按这个流程处理。

每次插入或删除空段时，都要同步维护两份索引。零长度空段不插入；与 $1$ 或 $N$ 相接的空段只进入 gap。座位坐标、长度和公式中的中间量统一使用 long long。

正确性与复杂度

我们保持以下状态不变量，gap 恰好包含当前全部极大连续空段，inside 恰好包含其中两侧都有观众的内部空段，groups 记录尚未离开的各组占座区间。

初始时只有 $[1,N]$ 这一空段，不变量成立。考虑一次入座。前面的推导给出了任意一个空段内的最优距离及取得该距离的最左位置。端点空段已经全部检查，内部空段中长度不超过 $G-2$ 的候选严格劣于最长空段，而长度 $G$、$G-1$ 中各自最左的空段又优于同长度的其他空段。因此程序比较的候选中一定包含全局最优解，并列时取最小左端点也符合题意。没有候选时，所有空段都短于 $k$，入座确实不可能。

成功入座只从一个极大空段中删去选中的连续座位，余下的至多两段由新观众隔开，恰好成为新的极大空段。离开时，释放的区间只可能连接两侧紧邻的空段，删除这两段后插入合并区间，恰好得到更新后的极大空段集合。其他空段不受影响，索引和组信息也同步更新，所以状态不变量在两类操作后继续成立。对操作次数归纳，程序的全部输出均正确。

若当前有 $m$ 组观众仍在座，极大空段至多有 $m+1\le q+1$ 个。每次操作只进行常数次有序集合查询、插入和删除，一次操作的时间为 $O(\log q)$。总时间复杂度为 $O(q\log q)$，空间复杂度为 $O(q)$，与座位数 $N$ 无关。

完整做法通过全部五个子任务，获得 100 分。

参考代码

以下代码与 solution/std.cpp 一致，使用 C++14。

#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    int q;
    cin >> n >> q;
    map<ll, ll> gap;
    set<pair<ll, ll>> inside;
    vector<pair<ll, ll>> groups(q + 1);

    auto add = [&](ll l, ll r) {
        if (l > r) return;
        gap[l] = r;
        if (l > 1 && r < n) inside.insert({r - l + 1, l});
    };
    auto erase = [&](ll l) {
        auto it = gap.find(l);
        ll r = it->second;
        if (l > 1 && r < n) inside.erase({r - l + 1, l});
        gap.erase(it);
    };
    add(1, n);

    for (int id = 1; id <= q; ++id) {
        int op;
        ll k;
        cin >> op >> k;
        if (op == 1) {
            ll best = -1, start = -1;
            auto check = [&](ll l, ll r) {
                ll len = r - l + 1;
                if (len < k) return;
                ll distance, x;
                if (l == 1 && r == n) {
                    distance = n + 1;
                    x = 1;
                } else if (l == 1) {
                    distance = len - k + 1;
                    x = 1;
                } else if (r == n) {
                    distance = len - k + 1;
                    x = n - k + 1;
                } else {
                    distance = (len - k) / 2 + 1;
                    x = l + (len - k) / 2;
                }
                if (distance > best || (distance == best && x < start)) {
                    best = distance;
                    start = x;
                }
            };

            if (!gap.empty()) {
                auto first = gap.begin(), last = prev(gap.end());
                if (first->first == 1) check(first->first, first->second);
                if (last->second == n) check(last->first, last->second);
            }
            if (!inside.empty()) {
                ll longest = inside.rbegin()->first;
                // 最优距离可能由相邻的两种长度同时取得。
                for (ll len = longest; len >= longest - 1; --len) {
                    auto it = inside.lower_bound({len, 0});
                    if (it != inside.end() && it->first == len) {
                        check(it->second, it->second + len - 1);
                    }
                }
            }

            cout << start << '\n';
            if (start != -1) {
                auto it = prev(gap.upper_bound(start));
                ll l = it->first, r = it->second;
                erase(l);
                add(l, start - 1);
                add(start + k, r);
                groups[id] = {start, start + k - 1};
            }
        } else {
            ll l = groups[k].first, r = groups[k].second;
            auto it = gap.lower_bound(l);
            if (it != gap.begin()) {
                auto left = prev(it);
                if (left->second == l - 1) {
                    ll new_left = left->first;
                    erase(new_left);
                    l = new_left;
                }
            }
            it = gap.lower_bound(r + 1);
            if (it != gap.end() && it->first == r + 1) {
                ll new_right = it->second;
                erase(it->first);
                r = new_right;
            }
            add(l, r);
            groups[k] = {0, 0};
        }
    }
    return 0;
}