我没有脸把这篇文章称作是「我」的题解。
难度非常的大。
说实话根本不知道怎么写，也无法理解。
再一次感受到人和巨神的区别。
「人跟人之间是有差距的。」
实在是无法理解，所以只能抄小粉兔的题解了。
可能等到我的能力有提升了之后才能理解这道题的正解吧。
话说有个sm打成了rt卡了我半天。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lwbt(_A) ((_A)&(-(_A)))
int q,loc[300005];
long long n,m,X[300005],Y[300005],ans[300005],arr[900005];
int len[300005],len2[300005],h[300005],tr[900005];
inline void add(int *_H,int _L,int _X,int _A){
while(_X<=_L){
_H[_X]+=_A;
_X+=lwbt(_X);
}
}
inline bool cmp(const int &_A,const int &_B){
return (X[_A]==X[_B])?(_A<_B):(X[_A]<X[_B]);
}
inline int srch(int *_H,int _L,int _X){
int l=1,r,mid,sm,rt;
while((l<=_L)&&(_H[l]<_X)){
l<<=1,rt=l;
}
r=l;
sm=_H[l>>=1];
while(l+1<r){
mid=(l+r)>>1;
if(mid>_L||_H[mid]+sm>=_X){
r=mid,rt=mid;
}else{
l=mid,sm+=_H[l];
}
}
rt=r;
return rt;
}
int st[300005],tp=0;
void init(){
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=q;++i){
scanf("%lld%lld",&X[i],&Y[i]);
loc[i]=i;
}
sort(loc+1,loc+1+q,cmp);
for(int i=1;i<m;++i){
add(tr,m-1,i,1);
}
for(int i=1;i<=n;++i){
len[i]=m-1;
}
for(int i=1;i<=q;++i){
if(X[loc[i-1]]!=X[loc[i]]){
while(tp){
add(tr,m-1,st[tp--],1);
}
}
if(Y[loc[i]]>len[X[loc[i]]]){
continue;
}
int pos=srch(tr,m-1,Y[loc[i]]);
ans[loc[i]]=(X[loc[i]]-1)*m+pos;
add(tr,m-1,pos,-1);
st[++tp]=pos;
--len[X[loc[i]]];
}
int it=0;
for(int i=1;i<=n;++i){
while(it<=q&&X[loc[it]]<i){
++it;
}
h[i]=it-1;
}
h[n+1]=q;
memset(tr,0,sizeof(tr));
for(int i=1;i<=n;++i){
len[i]=0,len2[i]=m-1;
}
len[n+1]=n;
for(int i=1;i<=n;++i){
add(tr+h[n+1],n+q,i,1);
arr[q+i]=i*m;
}
for(int i=1;i<=q;++i){
if(ans[i]){
int pos=srch(tr+h[n+1],n+q,X[i]);
add(tr+h[n+1],n+q,pos,-1);
add(tr+h[n+1],n+q,++len[n+1],1);
arr[h[n+1]+len[n+1]]=ans[i];
add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);
arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];
--len2[X[i]];
}else{
int pos=srch(tr+h[n+1],n+q,X[i]);
add(tr+h[n+1],n+q,pos,-1);
add(tr+h[n+1],n+q,++len[n+1],1);
if(Y[i]!=m){
int pos2=srch(tr+h[X[i]],h[X[i]+1]-h[X[i]],Y[i]-len2[X[i]]);
add(tr+h[X[i]],h[X[i]+1]-h[X[i]],pos2,-1);
ans[i]=arr[h[X[i]]+pos2];
add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);
arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];
}else{
ans[i]=arr[h[n+1]+pos];
}
arr[h[n+1]+len[n+1]]=ans[i];
}
}
for(int i=1;i<=q;++i){
printf("%lld\n",ans[i]);
}
}
int main(){
init();
return 0;
}