Solution 1 Splay
每行一颗Splay，没有动过的地方直接一段一个点。
最后一列单独一颗Splay。
暴力模拟即可。
Soluion 2 Splay II
我们考虑倒推。对于每个询问倒推出在第一次操作前时的位置。
考虑每个出队操作对答案的影响。
假设询问$(x, y)$，那么最后一列横坐标大于等于$x$的位置，横坐标都会加1.
第$x$行，纵坐标大于等于$y$的位置，纵坐标都会加1.
然后再把这个位置塞进$(x, y)$。
然后暴力模拟就好了。
Code
/**
* uoj
* Problem#334
* Accepted
* Time: 4027ms
* Memory: 25700k
*/
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
#define ll long long const int N = 3e5 + ; typedef class SplayNode {
public:
int val, tg, id;
SplayNode *ch[];
SplayNode *fa; SplayNode() { } void pushDown() {
for (int i = ; i < ; i++)
if (ch[i])
ch[i]->val += tg, ch[i]->tg += tg;
tg = ;
} int which(SplayNode* p) {
return p == ch[];
}
}SplayNode; SplayNode pool[N << ];
SplayNode* top = pool; SplayNode* newnode(int val, int id) {
top->val = val, top->id = id;
top->ch[] = top->ch[] = top->fa = NULL;
top->tg = ;
return top++;
} SplayNode* stps[N]; typedef class Splay {
protected:
void rotate(SplayNode* p) {
SplayNode *fa = p->fa, *ffa = fa->fa;
int df = fa->which(p);
SplayNode* ls = p->ch[df ^ ]; p->fa = ffa;
p->ch[df ^ ] = fa;
fa->fa = p;
fa->ch[df] = ls;
if (ls)
ls->fa = fa;
if (ffa)
ffa->ch[ffa->which(fa)] = p;
} void splay(SplayNode* p, SplayNode* fa) {
SplayNode** st = stps;
for (SplayNode* q = p; q; *(++st) = q, q = q->fa);
for ( ; st != stps; (*st)->pushDown(), st--);
for ( ; p->fa != fa; rotate(p))
if (p->fa->fa != fa)
rotate((p->fa->fa->which(p->fa) == p->fa->which(fa)) ? (p->fa) : (p));
if (!fa)
rt = p;
}
public:
SplayNode* rt; void insert(SplayNode*& p, SplayNode* fa, SplayNode* np) {
if (!p) {
p = np, np->fa = fa;
return;
}
if (p->tg)
p->pushDown();
insert(p->ch[np->val > p->val], p, np);
} boolean less_bound(int x) { // find the maximum number less than x and splay it
SplayNode* ret = NULL, *p = rt, *q = NULL;
while (p) {
q = p;
if (p->tg)
p->pushDown();
if (p->val < x)
ret = p, p = p->ch[];
else
p = p->ch[];
}
if (ret)
splay(ret, NULL);
else if (q)
splay(q, NULL);
return ret != NULL;
} void remove(SplayNode* p) {
splay(p, NULL);
if (!p->ch[]) {
rt = p->ch[];
if (rt)
rt->fa = NULL;
return;
} SplayNode* q = p->ch[];
while (q->ch[])
q = q->ch[];
splay(q, p);
q->ch[] = p->ch[];
if (p->ch[])
p->ch[]->fa = q;
rt = q;
} SplayNode* findMax() {
SplayNode* p = rt;
while (p && p->ch[]) {
if (p->tg)
p->pushDown();
p = p->ch[];
}
if (p)
splay(p, NULL);
return p;
} void insert(SplayNode* p) {
insert(rt, NULL, p);
splay(p, NULL);
} void getLis(SplayNode**& vs, SplayNode* p) {
if (!p)
return;
if (p->tg)
p->pushDown();
*(vs++) = p;
getLis(vs, p->ch[]);
getLis(vs, p->ch[]);
}
}Splay; int n, m, q;
Splay ls[N]; // maintain for (1, 1) - (n, m - 1)
Splay rs;
int xs[N], ys[N];
ll res[N]; inline void init() {
scanf("%d%d%d", &n, &m, &q);
for (int i = ; i <= q; i++)
scanf("%d%d", xs + i, ys + i);
} int uf[N]; int find(int x) {
return (uf[x] == x) ? (x) : (uf[x] = find(uf[x]));
} inline void solve() {
for (int i = ; i <= q; i++)
uf[i] = i; SplayNode *p;
for (int i = q; i; i--) {
int x = xs[i], y = ys[i];
while ((p = rs.findMax()) && p->val == n)
uf[find(p->id)] = i, rs.remove(p);
if (rs.rt) {
if (rs.less_bound(x)) {
p = rs.rt->ch[];
if (p)
p->val++, p->tg++;
} else
rs.rt->val++, rs.rt->tg++;
}
if (y == m) {
rs.insert(newnode(x, i));
} else {
Splay& sp = ls[x];
if (sp.rt) {
if (sp.less_bound(y)) {
p = sp.rt->ch[];
if (p)
p->val++, p->tg++;
} else
sp.rt->val++, sp.rt->tg++;
}
while ((p = sp.findMax()) && p->val == m)
rs.insert(newnode(x, p->id)), sp.remove(p);
sp.insert(newnode(y, i));
}
} SplayNode **pp, **pq;
for (int i = ; i <= n; i++) {
pp = stps;
ls[i].getLis(pp, ls[i].rt);
for (pq = stps; pq != pp; pq++)
res[(*pq)->id] = (i - ) * 1ll * m + (*pq)->val;
}
pp = stps;
rs.getLis(pp, rs.rt);
for (pq = stps; pq != pp; pq++)
res[(*pq)->id] = (*pq)->val * 1ll * m;
for (int i = ; i <= q; i++)
printf(Auto"\n", res[find(i)]);
} int main() {
init();
solve();
return ;
}
Splay
Solution 3 BIT
考虑删掉的位置我们留下，如果我们知道所有按顺序被加进这一行的人，那么我们查找第$k$列的人相当于求第$k$大值。
我们可以利用树状数组预处理出每一行除去最后一列，每个询问是第几个加入这一行的数（原来的数依次看做第一个，第二个，...）。
然后开始处理询问。用类似的方法维护最后一列。
这样可以算每次询问，最后一列被拿走的数，以及当且行被加入的数。
Code
/**
* uoj
* Problem#334
* Accepted
* Time: 1673ms
* Memory: 32808b
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} const int bzmax = ;
const int N = 3e5 + ; typedef class IndexedTree {
public:
int *ar;
int s; IndexedTree() { }
IndexedTree(int s):s(s) {
ar = new int[(s + )];
pfill(ar, ar + s + , );
} void add(int idx, int val) {
for ( ; idx <= s; idx += ((-idx) & idx))
ar[idx] += val;
} int kth(int k) {
int rt = , cur = ;
for (int b = ( << (bzmax - )); b; b >>= )
if ((rt | b) <= s && cur + ar[rt | b] < k)
rt += b, cur += ar[rt | b];
return rt + ;
}
}IndexedTree; #define ll long long
#define pii pair<int, int>
#define fi first
#define sc second int n, m, q, K;
int rk[N];
IndexedTree it;
pii qs[N];
vector<ll> lst;
vector<ll> vs[N];
vector<pii> ms[N]; inline void init() {
scanf("%d%d%d", &n, &m, &q);
K = max(n, m) + q;
it = IndexedTree(K);
for (int i = ; i <= q; i++) {
scanf("%d%d", &qs[i].fi, &qs[i].sc);
if (qs[i].sc < m)
ms[qs[i].fi].push_back(pii(qs[i].sc, i));
}
} inline void solve() {
for (int i = ; i <= K; i++)
it.add(i, );
for (int i = ; i <= n; i++) {
for (vector<pii> :: iterator it = ms[i].begin(); it != ms[i].end(); it++)
::it.add(rk[it->sc] = ::it.kth(it->fi), -);
for (vector<pii> :: iterator it = ms[i].begin(); it != ms[i].end(); it++)
::it.add(rk[it->sc], );
} ll res;
for (int i = , x, y, p; i <= q; i++) {
x = qs[i].fi, y = qs[i].sc;
it.add(p = it.kth(x), -);
res = ((p <= n) ? (p * 1ll * m) : (lst[p - n - ]));
if (y < m) {
vs[x].push_back(res);
res = ((rk[i] <= m - ) ? ((x - ) * 1ll * m + rk[i]) : vs[x][rk[i] - m]);
}
lst.push_back(res);
printf(Auto"\n", res);
}
} int main() {
init();
solve();
return ;
}