考虑每行维护一棵线段树，最后一列单独维护。
每次出队的时候更新。
但是空间喜闻乐见地炸掉了。
动态开点即可，用 \(0\) 表示还在，用 \(1\) 表示被删了。
则需要支持的操作就是查找第 \(k\) 个 \(0\) 的位置，非常简单。
注意出队的时候，要把这一行最右边新增的点插入。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
const int N = 3e5;
int n,m,q;
struct node
{
int sum;
int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5],seg_tot;
vector<long long> vec[N + 5];
void insert(int x,int &p,int tl,int tr)
{
static int tot = 0;
!p && (p = ++tot),++seg[p].sum;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int query(int k,int p,int tl,int tr)
{
if(tl == tr)
return tl;
int mid = tl + tr >> 1;
int sum = (mid - tl + 1) - seg[seg[p].ls].sum;
return k <= sum ? query(k,seg[p].ls,tl,mid) : query(k - sum,seg[p].rs,mid + 1,tr);
}
long long ans,cur;
int main()
{
scanf("%d%d%d",&n,&m,&q);
int x,y;
for(register int i = 1;i <= q;++i)
{
scanf("%d%d",&x,&y);
if(y == m)
{
insert(ans = query(x,rt[0],1,n + q),rt[0],1,n + q);
vec[0].push_back(ans = ans <= n ? (long long)ans * m : vec[0][ans - n - 1]);
}
else
{
insert(ans = query(y,rt[x],1,m + q),rt[x],1,m + q);
ans = ans < m ? (long long)(x - 1) * m + ans : vec[x][ans - m];
insert(cur = query(x,rt[0],1,n + q),rt[0],1,n + q);
vec[x].push_back(cur = cur <= n ? (long long)cur * m : vec[0][cur - n - 1]),vec[0].push_back(ans);
}
printf("%lld\n",ans);
}
}