题解：
考场实际得分：45
重新看了一下，发现至少80分是很好拿的
对于前30% 暴力
另20% 显然离线搞一下就可以了（大概当初连离线是啥都不知道）
另另30%其实只要维护第一行和最后一列就可以了，显然可以用splay来完成加点删点
满分做法：
1 .splay(是看了题解才知道了）
类似线段树的动态开点，splay也可以先把一个节点作为一段序列的维护，当使用时再裂点
2.动态开点线段树
#upd：8.8写了一下
写了30min，debug了30min左右
思路挺简单的，动态开点线段树维护，对最后一列开一颗线段树
然后细节就是最后一列，注意每次对某一行操作的时候要把正确的最后一位填入到当前行
查询时如果问最后一列，在那颗特殊的线段树里查
#define比void还是快好多啊
洛谷这个评测是什么鬼。。为什么一模一样的总时间差2s
#include <bits/stdc++.h> using namespace std; #define ll long long #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } template<class T>IL void read(T &x) { rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48); while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; } const int N=3.1e5; const int N2=1.5e7; int v[N2],s[N2],rs[N2],ls[N2]; ll now[N2]; int cnt,n,n1,m,q,e[N],root[N]; struct re{ ll a,b; }jl; #define min(x,y) ((x)<(y)?(x):(y)) struct sgt{ int m; // #define mid ((h+t)>>1) /*IL void sc(int &x,int h,int t) { if (x) return; x=++cnt; if (h<=m) v[x]=min(t,m)-h+1; } */ #define sc(x,h,t) if (!(x)) {(x)=++cnt;if ((h)<=(m)) v[x]=min(t,m)-h+1;} void query(rint x,rint h,rint t,int k,int z) { if (h==t) { if (k!=v[x]) { jl=(re){0,0}; return; } v[x]-=z; jl=(re){h,now[x]}; return; } rint &l1=ls[x],&l2=rs[x]; rint mid=(h+t)/2,mid2=mid+1; sc(l1,h,mid); sc(l2,mid2,t); v[x]-=z; if (v[l1]>=k) query(l1,h,mid,k,z); else query(l2,mid+1,t,k-v[l1],z); } void change(int x,int h,int t,int pos,ll k) { if (h==t) { v[x]=1; now[x]=k; return; } rint mid=(h+t)/2,mid2=mid+1; if (pos<=mid) { sc(ls[x],h,mid); change(ls[x],h,mid,pos,k); } else { sc(rs[x],mid2,t); change(rs[x],mid2,t,pos,k); } v[x]++; } }S[N]; int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); read(n1); read(m); read(q); n=max(m,n1)+q; rep(i,1,n1) e[i]=m; e[n1+1]=n1; rep(i,1,n1) root[i]=i,v[i]=m,S[i].m=m; S[n1+1].m=n1; root[n1+1]=n1+1,v[n1+1]=n1; cnt=n1+1; rep(i,1,q) { int x,y; read(x); read(y); ll ans,ans2; re k; S[x].query(root[x],1,n,m,1); if (y!=m) { S[x].query(root[x],1,n,y,1); k=jl; if (!k.b) ans=1ll*(x-1)*m+k.a; else ans=k.b; } else { S[n1+1].query(root[n1+1],1,n,x,0); k=jl; if (!k.b) ans=m*k.a; else ans=k.b; } cout<<ans<<endl; S[n1+1].query(root[n1+1],1,n,x,1); k=jl; if (!k.b) ans2=1ll*k.a*m; else ans2=k.b; S[x].change(root[x],1,n,++e[x],ans2); S[n1+1].change(root[n1+1],1,n,++e[n1+1],ans); } return 0; }