P3960 [NOIP 2017 提高组] 列队 题解
Getaway_Car
·
·
题解
本文提供一种动态开点线段树做法。
这道题写的时候调了很久，原因是 while(q--)，而处理询问时又用到了 q。
另外，sjx 在讲义中这样写：
为了解决空间问题，我们可以离线所有查询、删除和追加操作，然后 one by one 用线段树处理每个序列，每一个处理完后回滚到初始状态，再处理下一个。
为了解决空间问题，直接动态开点不就是了。
我们发现，每一行是相对独立的，所以考虑单独处理。对于每一行的前 m - 1 个元素与最后一列，我们需要维护单点查询、单点删除与末尾插入。暴力的单点删除显然不可取，那么容易想到用线段树标记每个元素是否已被删除，查询时用线段树二分找到被查询元素的真实位置。由于有末尾插入的操作，所以我们可以对每棵线段树先多开 q 个位置。对于新加入的元素，我们并不把它实际地插入到线段树中，而是放到这一行（或列）对应的一个 vector 里面。
具体地，对于一次操作，需要进行以下操作（假设 y \ne m）：
- 在第 x 棵线段树上二分找到 a_{x, y} 的真实位置，从而得到 a_{x, y} 的值（并输出）；
- 将 a_{x, y} 插入到第 n + 1 棵线段树（用于维护最后一列）的末尾；
- 从第 x 棵线段树中删除 a_{x, y}；
- 在第 n + 1 棵线段树上二分找到 a_{x, m} 的位置，从而得到 a_{x, m} 的值；
- 将 a_{x, m} 插入到第 x 棵线段树的末尾；
- 从第 n + 1 棵线段树中删除 a_{x, m}。
时间复杂度 $O(q \log n)$。
关于线段树节点数量，估算下来理论上限是 $1.2 \times 10^7$，而实测下来 $4 \times 10^6$ 已经足够了。
---
在代码实现中，线段树中的 ``0`` 指未被删除，``1`` 指已被删除，这样处理的目的是在末尾插入元素时不需要访问线段树元素。
由于每个询问一定有解，所以线段树二分时没必要判断无解，整个过程也不需要考虑下标越界的问题，没什么细节，个人认为比较好写。
```cpp
#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;
}
```