题解 P3960 【列队】
_rqy
2017-11-13 17:43:45
qwq据说正解是树状数组但是我完全不会。。。
蒟蒻只会用splay做qwq。
我们观察每一行除了最后一个数之外的数在操作中是如何变化的。
如果出队在(x,y)，那么第x行（除了最后一个数）会弹出第y个数，它后面的数依次左移，再在最后插入一个数（就是最后一列当前的第x个数）；然后，对于最后一列，我们要弹出第x个数（插入到第x行），再在最后插入一个数（就是刚出队的那个）。
所以，我们无论是对于行还是列，都要执行两种操作：第一，弹出第k个数，第二，在尾部插入一个数。这可以用splay来实现。
但是这样的话空间复杂度是$O(nm)$。
我们发现有些人从始至终都是左右相邻的，这些人对应的splay节点可以合并。
于是我们在维护splay的时候，所有连续的数的区间我们用一个节点维护，记录这个节点表示的区间的左右端点；
如果我们发现要弹出的数在某个节点内部，我们就把它拆开，拆成3个节点（其中中间那个节点只有一个数，就是我们要的那个数），拆点的过程可以直接跑splay上的insert，删除中间那个节点就是splay上的删除。
总时间复杂度为$O(nlogn)$。
代码：
```cpp
#include <cstdio>
namespace rqy{ //命名空间是为了防止和某些奇怪的变量命名冲突，也可以去掉
typedef long long LL;
const int N = 3000500;
int fa[N], son[N][2], cnt;
LL l[N], r[N], siz[N]; //l, r表示区间左右端点，此处左闭右开（个人习惯）
struct Splay{
int root;
inline int newNode(LL ll, LL rr) { //ll, rr表示新节点的区间左右端点
++cnt;
fa[cnt] = son[cnt][0] = son[cnt][1] = 0;
siz[cnt] = (r[cnt] = rr) - (l[cnt] = ll);
return cnt;
}
inline void init(LL ll, LL rr) { //初始化树，只有一个对应[ll,rr)的根节点。
root = newNode(ll, rr);
}
inline void upd(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + r[x] - l[x]; }
inline int dir(int x) { return son[fa[x]][1] == x; } //x是fa[x]的哪个儿子
inline void rotate(int x) { //没什么好说的
int d = dir(x), f = fa[x];
fa[x] = fa[f];
if (f == root) root = x;
else son[fa[f]][dir(f)] = x;
if (son[f][d] = son[x][d ^ 1]) fa[son[f][d]] = f;
fa[son[x][d ^ 1] = f] = x;
upd(f);
upd(x);
}
void splay(int x) { //同上
for (; fa[x]; rotate(x))
if (fa[fa[x]]) rotate(dir(x) == dir(fa[x]) ? fa[x] : x);
}
int splitNode(int x, LL k) { //把节点x分裂，分裂后x的区间里前k个数还在x节点上，
k += l[x]; //后边的数对应新节点（即该函数返回值）
int y = newNode(k, r[x]);
r[x] = k;
if (son[x][1] == 0) {
fa[son[x][1] = y] = x;
} else {
int t = son[x][1];
while (son[t][0]) t = son[t][0];
fa[son[t][0] = y] = t;
while (t != x) upd(t), t = fa[t];
}
splay(y);
return y;
}
LL popKth(LL k) { //弹出第k大数
int o = root;
while (1) {
if (siz[son[o][0]] >= k) {
o = son[o][0];
} else {
k -= siz[son[o][0]];
if (k <= r[o] - l[o]) {
if (k != r[o] - l[o]) splitNode(o, k);
if (k != 1) o = splitNode(o, k - 1);
break;
} else {
k -= r[o] - l[o];
o = son[o][1];
}
}
}
splay(o);
fa[son[o][0]] = fa[son[o][1]] = 0;
if (!son[o][0]) { //splay删除
root = son[o][1];
} else {
int t = son[o][0];
while (son[t][1]) t = son[t][1];
splay(t);
upd(root = fa[son[t][1] = son[o][1]] = t);
}
return l[o];
}
void pushBack(LL k) { //尾部插入数k
int y = newNode(k, k + 1);
if (!root) {
root = y;
} else {
int o = root;
while (son[o][1]) o = son[o][1];
splay(o);
upd(fa[son[o][1] = y] = o);
}
}
};
Splay s[N];
void main() {
cnt = 0;
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for (LL i = 1; i <= n; ++i) s[i].init((i - 1) * m + 1, i * m);
s[0].init(m, m + 1);
for (LL i = 2; i <= n; ++i) s[0].pushBack(i * m);
int x, y;
LL p;
while (q--) {
scanf("%d%d", &x, &y);
s[x].pushBack(s[0].popKth(x));
printf("%lld\n", p = s[x].popKth(y));
s[0].pushBack(p);
}
}
};
int main() {
rqy::main();
return 0;
}
```