题意分析
显然，第 $x$ 行的操作仅影响第 $x$ 行和第 $m$ 列。
因此考虑用 $i$ 个数据结构维护第 $i$ 行的前 $m-1$ 个学生，再用单独的一个维护最后一列。
那么这就是一个序列维护问题，考虑平衡树或权值线段树。
但是直接做空间会炸掉，因此可以优化。
- 对于平衡树，可以用一个节点存储一段区间，使用时分裂。
- 对于权值线段树，可以动态开点。
AC 代码
动态开点权值线段树写法。
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<random>
#define int long long
using namespace std;
typedef long long ll;
constexpr const int N=3e5,M=3e5,Q=3e5;
int n,m,q;
int deleted[N*20],L[N*20],R[N*20];
void change(int &x,int l,int r,int pos){
if(!x){
static int cnt;
x=++cnt;
}
deleted[x]++;
if(l==r){
return;
}
int mid=l+r>>1;
if(pos<=mid){
change(L[x],l,mid,pos);
}else{
change(R[x],mid+1,r,pos);
}
}
int query(int x,int l,int r,int k){
if(l==r){
return l;
}
int mid=l+r>>1;
int lsum=mid-l+1-deleted[L[x]];
if(lsum>=k){
return query(L[x],l,mid,k);
}else{
return query(R[x],mid+1,r,k-lsum);
}
}
int rot[N];
vector<ll>row[N+1];
ll remove(int x, int y){
int pos=query(rot[x],1,max(n,m)+q,y);
change(rot[x],1,max(n,m)+q,pos);
if(pos<m){
return 1ll*(x-1)*m+pos;
}else{
return row[x][pos-m];
}
}
int rotCol;
vector<ll>col;
ll remove2(int x){
int pos=query(rotCol,1,max(n,m)+q,x);
change(rotCol,1,max(n,m)+q,pos);
if(pos<=n){
return 1ll*pos*m;
}else{
return col[pos-n-1];
}
}
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
if(y==m){
ll ans=remove2(x);
col.push_back(ans);
cout<<ans<<'\n';
}else{
ll ans=remove(x,y);
ll ans2=remove2(x);
row[x].push_back(ans2);
col.push_back(ans);
cout<<ans<<'\n';
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
