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

这道题写的时候调了很久，原因是 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}$。

$y = m$ 时也类似，不再展开阐述。

时间复杂度 $O(q \log n)$。

关于线段树节点数量，估算下来理论上限是 $1.2 \times 10^7$，而实测下来 $4 \times 10^6$ 已经足够了。

在代码实现中，线段树中的 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;
}

C89 树状数组+二分 P3960 [NOIP2017 提高组] 列队

// 树状数组+二分 O(N*logN*logN)
#include <iostream> 
#include <cstring> 
#include <algorithm> 
#include <vector> 
using namespace std; 

#define int long long 
const int N=300005; 
int read(){ 
  int x=0,f=1;char c=getchar(); 
  while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 
  while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 
  return x*f; 
} 
int n,m,q,mx,x[N],y[N]; 
struct Q{ 
  int y,iq;        //列下标,第i个询问 
}; 
vector<Q> v[N];    //存储询问信息 
int col[N];        //存储查询的列下标 
int s[N*2];        //权值树状数组 
vector<int> qu[N]; //新队列 
int mcol,num;      //第m列数,离队数 

void change(int x,int k){ //向后修 
  while(x<=mx) s[x]+=k, x+=x&-x; 
} 
int query(int x){ //向前查 
  int t=0; 
  while(x) t+=s[x], x-=x&-x; 
  return t; 
} 
int Bsearch(int x){ //二分查找≥x的最小值 
  int l=-1,row=mx+1,mid; 
  while(l+1<row){ 
    mid=(l+row)>>1; 
    query(mid)>=x?row=mid:l=mid; 
    } 
  return row; 
} 
signed main(){ 
  n=read();m=read();q=read(); mx=max(m,n)+q; //树节点个数 
  for(int i=1;i<=q;i++){ 
    x[i]=read(); y[i]=read(); 
    if(y[i]!=m)              //不在第m列,则按行存储询问信息 
      v[x[i]].push_back({y[i],i}); 
  } 
  for(int i=1;i<=mx;i++) change(i,1); //树节点初始为1 
  for(int i=1;i<=n;i++){        //逐行处理 
    for(Q t:v[i]){ 
      col[t.iq]=Bsearch(t.y);   //树上二分,存储查询列下标 
      change(col[t.iq],-1);     //树上删除col的贡献 
    } 
    for(Q t:v[i]) 
      change(col[t.iq],1);      //还原树状数组,以免影响下一行 
  } 
    for(int i=1,row;i<=q;i++){ //枚举询问i 
      row=Bsearch(x[i]);          //树上二分,找出查询行下标 
      change(row,-1);             //树上删除row的贡献 
      if(row<=n) mcol=row*m;      //mcol来自原队列 
      else mcol=qu[0][row-n-1];   //mcol来自新队列 
      if(y[i]==m) num=mcol;       //离队数mcol 
      else{                       //离队数不是mcol 
        qu[x[i]].push_back(mcol); //mcol压入新队列 
        if(col[i]<m) num=(x[i]-1)*m+col[i]; //num来自原队列 
        else num=qu[x[i]][col[i]-m];        //num来自新队列 
      } 
      qu[0].push_back(num);                 //num压入新队列 
      cout<<num<<endl; 
    } 
}

动态开点线段树 O(nlogn)

// 用vector开n+1个新队列，动态开n+1颗线段树 O(nlogn)
#include <iostream> 
#include <cstring> 
#include <algorithm> 
#include <vector> 
using namespace std; 

#define LL long long 
#define mid ((l+r)>>1) 
const int N=300005,M=N*40; 
int n,m,q,x,y,tot,mx; 
int rt[N],ls[M],rs[M],sum[M]; //权值线段树 
vector<LL> qu[N]; //新队列 
LL mcol,num;      //第m列数,离队数 

void change(int &x,int l,int r,int p){ //点修 
   if(!x) x=++tot; //开点 
   sum[x]++;       //从根到p的节点均+1 
   if(l==r) return; 
   if(p<=mid) change(ls[x],l,mid,p); 
   else change(rs[x],mid+1,r,p-t); 
} 
int query(int x,int l,int r,int p){ //点查 
   if(l==r) return l;        //返回p的下标位置 
   int t=mid-l+1-sum[ls[x]]; //左区间的空穴数 
   if(p<=t) return query(ls[x],l,mid,p); 
   else return query(rs[x],mid+1,r,p-t); 
} 
LL work1(int x,LL y){ //num在第m列 
   int row=query(rt[0],1,mx,x); //x在第m列的行下标 
   change(rt[0],1,mx,row); 
   if(row<=n) mcol=1LL*row*m;   //mcol来自原队 
   else mcol=qu[0][row-n-1];    //mcol来自新队qu[0] 
   qu[0].push_back(y?y:mcol);   //num压入新队qu[0] 
   return mcol;                 //返回mcol 
} 
LL work2(int x,int y){ //num不在第m列 
   int col=query(rt[x],1,mx,y);   //y在第x行的列下标 
   change(rt[x],1,mx,col); 
   if(col<m) num=1LL*(x-1)*m+col; //num来自原队 
   else num=qu[x][col-m];         //num来自新队qu[x] 
   qu[x].push_back(work1(x,num)); //mcol压入新队qu[x] 
   return num;                    //返回num 
} 
int main(){ 
   scanf("%d%d%d",&n,&m,&q); mx=max(n,m)+q; 
   while(q--){ 
      scanf("%d%d",&x,&y); 
      printf("%lld\n",y==m?work1(x,0):work2(x,y)); 
   } 
}