P3960 [NOIP 2017 提高组] 列队题解
P3960 [NOIP 2017 提高组] 列队题解
大致思路：
方法1：
首先，问题分成两个操作。
-
向左看齐（行内的单点查找和删除）。
-
向前看齐（最后一列的单点查找和删除）。
我们把图分成两个部分：
-
-
最右侧的
n 这一列。
考虑最后一列有
之后首先判断要移走的列是不是最后一列，如果是，则这次列队中出队的人的编号，就已经找到了（也就是最后一列找到的位置的编号），把
如果等于
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 6e6 + 20;
int n, m, q, cnt, rt[N / 2];
struct node
{
int s, ls, rs;
} t[N]; // 可持久化线段树节点
LL ID[N], pos;
vector<LL> G[N / 2]; // 每行末尾的新编号
#define mid (l + r >> 1)
#define ls t[p].ls
#define rs t[p].rs
#define lson ls, l, mid
#define rson rs, mid + 1, r
int F(int k, int &p, int l, int r)
{ // 去掉第k大（初始时每个区间都是全部点都在）
if (!p)
t[p = ++cnt].s = r - l + 1; // 新建一个点，长度是全部
--t[p].s; // 每次减少1（第k大在这个区间里，把他移走等效于区间长度减少1）
if (l == r)
return l; // 找到点了（这也是第k大），返回下标
int sl = ls ? t[ls].s : mid - l + 1; // 如果左子树存在，就取左子树里剩余的，否则剩余的视为全部长度
if (sl >= k)
return F(k, lson); // 线段树上二分，看第k大在哪颗子树，就移走他
return F(k - sl, rson);
}
// ID_i: 最后一列第 i 个位置的编号
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i)
ID[i] = 1ll * i * m;
for (int i = 1; i <= q; ++i)
{
int x, y;
cin >> x >> y;
int kk = F(x, rt[0], 1, n + q); // 倒着考虑，先最后一列上下对齐。找到并去掉最后一列的第x大
// 找行，一共最多 n+q 行，找当前图里的第 x 行（之前如果已经取了x或以下的，这时候找到的行就不一样了）
if (y == m)
ID[n + i] = ID[kk]; // 如果移走的元素是第m列，就不用左右对齐了。
else
{
G[x].push_back(ID[kk]); // 把填进去的元素放在 x 行末尾
pos = F(y, rt[x], 1, m + q); // 考虑前面的操作。第 x 行左右对齐，去掉第 y 个
if (pos < m)
ID[n + i] = 1ll * (x - 1) * m + pos; // 如果位置在原图里，且不是最后一个，直接算出位置，变成最后一列最下面的一个位置
// 如果恰好是最后一个位置m，肯定不是第一次操作这行。之前操作过一次G[x]已经有最后一个了
else
ID[n + i] = G[x][pos - m]; // 否则新的行最后一共元素就是第x行从前往后加入的
}
cout << ID[n + i] << '\n';
}
}方法2：
显然可以使用平衡树，我们需要维护两种操作：
操作
操作
因为我们不可能对于每个点暴力使用平衡树，不然你就需要看
然后我们考虑如何维护每一行，我们会发现