感觉是至今为止做到的最难的数据结构题
什么分块，嵌套，可持久化都没有这题给人的第一感觉难
这题每个数据开一个点都开不下。
考场上见到这题基本上一脸懵逼，想了很久写了个但是不能优化的算法，结果没开LL只有30分
用线段树维护每一行和最后一列，支持单点rank 和insert 两种操作
最大长度为
动态开点减少内存，空间复杂度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
using namespace std;
const int N=300050;
struct node {int l,r,sz,id;bool f;} t[N*60];
int n,m,T,cnt=0,idx=0,rt[N],sz[N],pos,u,v;
LL w[N<<2];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void build(int &o,int l,int r,int f)
{
o=++cnt;
if (l==r)
{
t[o].sz=(!f&&r<m)||(f&&r<=n);
return;
}
int mid=(l+r)>>1;
build(t[o].l,l,mid,f);
build(t[o].r,mid+1,r,f);
t[o].sz=t[t[o].l].sz+t[t[o].r].sz;
}
LL ask(int &o,int pre,int l,int r,int f)
{
if (!t[o].f) o=++cnt,t[o]=t[pre],t[o].f=1;
if (l==r)
{
t[o].sz=0;
if (!f&&r<m) return (LL)(u-1)*m+l;
if (f&&r<=n) return (LL)r*m;
return w[t[o].id];
}
int num=t[t[o].l].sz,mid=(l+r)>>1;LL ret;
if (pos<=num)
ret=ask(t[o].l,t[pre].l,l,mid,f);
else
pos-=num,ret=ask(t[o].r,t[pre].r,mid+1,r,f);
t[o].sz=t[t[o].l].sz+t[t[o].r].sz;
return ret;
}
void insert(int &o,int pre,int l,int r,LL x)
{
if (!t[o].f) o=++cnt,t[o]=t[pre],t[o].f=1;
if (l==r)
{
w[++idx]=x;
t[o].id=idx,t[o].sz=1;
return;
}
int mid=(l+r)>>1;
if (pos<=mid)
insert(t[o].l,t[pre].l,l,mid,x);
else
insert(t[o].r,t[pre].r,mid+1,r,x);
t[o].sz=t[t[o].l].sz+t[t[o].r].sz;
}
int main()
{
n=read(),m=read(),T=read();
int maxs=max(n,m)+T;
build(rt[0],1,maxs,0);
for(int i=1;i<=n;i++) rt[i]=++cnt,t[cnt]=t[rt[0]],t[cnt].f=1;
for(int i=1;i<=n;i++) sz[i]=m-1;sz[n+1]=n;
build(rt[n+1],1,maxs,1);
while (T--)
{
u=read(),v=read();
if (v==m)
{
LL x;
pos=u,x=ask(rt[n+1],rt[n+1],1,maxs,1);
printf("%lld\n",x);
pos=++sz[n+1],insert(rt[n+1],rt[n+1],1,maxs,x);
}
else
{
LL x,w;
pos=v,x=ask(rt[u],rt[u],1,maxs,0);
printf("%lld\n",x);
pos=u,w=ask(rt[n+1],rt[n+1],1,maxs,1);
pos=++sz[u],insert(rt[u],rt[u],1,maxs,w);
pos=++sz[n+1],insert(rt[n+1],rt[n+1],1,maxs,x);
}
}
return 0;
}