P3960 [NOIP 2017 提高组] 列队 题解

本文提供一种动态开点线段树做法。

---

这道题写的时候调了很久，原因是 while(q--)，而处理询问时又用到了 。

另外，sjx 在讲义中这样写：

为了解决空间问题，我们可以离线所有查询、删除和追加操作，然后 one by one 用线段树处理每个序列，每一个处理完后回滚到初始状态，再处理下一个。

为了解决空间问题，直接动态开点不就是了。

---

我们发现，每一行是相对独立的，所以考虑单独处理。对于每一行的前 个元素与最后一列，我们需要维护单点查询、单点删除与末尾插入。暴力的单点删除显然不可取，那么容易想到用线段树标记每个元素是否已被删除，查询时用线段树二分找到被查询元素的真实位置。由于有末尾插入的操作，所以我们可以对每棵线段树先多开 个位置。对于新加入的元素，我们并不把它实际地插入到线段树中，而是放到这一行（或列）对应的一个 vector 里面。

具体地，对于一次操作，需要进行以下操作（假设 ）：

• 在第 棵线段树上二分找到 的真实位置，从而得到 的值（并输出）；
• 将 插入到第 棵线段树（用于维护最后一列）的末尾；
• 从第 棵线段树中删除 ；
• 在第 棵线段树上二分找到 的位置，从而得到 的值；
• 将 插入到第 棵线段树的末尾；
• 从第 棵线段树中删除 。

时也类似，不再展开阐述。

时间复杂度 。

关于线段树节点数量，估算下来理论上限是 ，而实测下来 已经足够了。

---

在代码实现中，线段树中的 0 指未被删除，1 指已被删除，这样处理的目的是在末尾插入元素时不需要访问线段树元素。

由于每个询问一定有解，所以线段树二分时没必要判断无解，整个过程也不需要考虑下标越界的问题，没什么细节，个人认为比较好写。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, q, x, y, rt[300005], ps, val;
vector<int> num[300005];
struct Segtree {
    int tr[4000005], ls[4000005], rs[4000005], cnt;
    void update(int l, int r, int& p, int s) {
        if(!p) p = ++cnt;
        if(l == r) return tr[p] = 1, void();
        int mid = (l + r) >> 1;
        if(s <= mid) update(l, mid, ls[p], s);
        else update(mid + 1, r, rs[p], s);
        tr[p] = tr[ls[p]] + tr[rs[p]];
        return;
    }
    int query(int l, int r, int& p, int d) {
        if(!p) p = ++cnt;
        if(l == r) return l;
        int mid = (l + r) >> 1, tmp = (mid - l + 1) - tr[ls[p]];
        if(d > tmp) return query(mid + 1, r, rs[p], d - tmp);
        else return query(l, mid, ls[p], d);
    }
} tr;

signed main() {
    scanf("%lld %lld %lld", &n, &m, &q);
    for(int _ = 1; _ <= q; ++_) {
        scanf("%lld %lld", &x, &y);
        if(y < m) {
            ps = tr.query(1, m - 1 + q, rt[x], y); // step 1
            if(ps < m) val = (x - 1) * m + ps;
            else val = num[x][ps - m];
            printf("%lld\n", val);
            num[n + 1].push_back(val); // step 2
            tr.update(1, m - 1 + q, rt[x], ps); // step 3
            ps = tr.query(1, n + q, rt[n + 1], x); // step 4
            if(ps <= n) val = ps * m;
            else val = num[n + 1][ps - n - 1];
            num[x].push_back(val); // step 5
            tr.update(1, n + q, rt[n + 1], ps); // step 6
        }
        else {
            ps = tr.query(1, n + q, rt[n + 1], x); // step 1
            if(ps <= n) val = ps * m;
            else val = num[n + 1][ps - n - 1];
            printf("%lld\n", val);
            num[n + 1].push_back(val); // step 2
            tr.update(1, n + q, rt[n + 1], ps); // step 3
        }
    }
    return 0;
}