代码

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define mid ((l+r)>>1)
using namespace std;  typedef long long ll;
const int maxn=3e5+5,maxm=6e6+5;
int n,m,q,rt[maxn],ls[maxm],rs[maxm],seg[maxm],cnt;
ll id[maxn<<1];
vector<ll> e[maxn];
int que(const int&k,const int&l,const int&r,int&pos){
      if(!pos)pos=++cnt,seg[pos]=r-l+1;
      --seg[pos];
      if(l==r)return l;
      int g=ls[pos]?seg[ls[pos]]:mid-l+1;
      return g>=k?que(k,l,mid,ls[pos]):que(k-g,mid+1,r,rs[pos]);
}
int main(){
      ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      cin>>n>>m>>q;
      for(int t=1;t<=n;++t) id[t]=1ll*t*m;
      for(int t=n+1,N=n+q,M=m+q,x,y,ans;q--;cout<<id[t++]<<'\n'){
	    cin>>x>>y;
	    if(y==m) id[t]=id[ans=que(x,1,N,rt[0])];
	    else id[t]=(ans=que(y,1,M,rt[x]))<m?(x-1ll)*m+ans:e[x][ans-m], e[x].push_back(id[que(x,1,N,rt[0])]);
      }
      return 0;
}

评测结果