[noip2017]列队

线段树 主席树 vector

题面

无人不知，无人不晓

解析

想想如何简化题目中的操作。
一个人到$(n,m)$，暴力模拟的复杂度是$O(n+m)$。
考虑节省掉移动整行整列的复杂度。

实际上，不如让一个人移走后留下的位置空着。
这样一行最多只有$6*10^5$，是可以维护的。

于是用$n$棵线段树维护一下每一行中，区间内有多少个空位置。
这样就可以查出一行的第$k$个在哪里。

当然，如果每行线段树都开全，空间复杂度$O(nm)$开不下。
所以需要动态开点。

注意到只有$n$行和第$m$列有可能新加入数。
可以用$vector$存一下，每行新加入了什么数（第$m$列不包含在内）。
还有一个$vector$存第$m$列新加入的数。

另外，删掉$vector$中的数也是$O(n)$级别的。所以每行的线段树也要维护$vector$中的空位置。

这么以来，操作就转化为在数据结构的基础上模拟了。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define pb push_back
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=3e5+100;
int n,m,q,t[N*100],tot,rt[N*100],tim,ls[N*100],rs[N*100];
vector<ll>V[N];
il ll gi()
{
  re ll x=0,t=1;
  re 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;
}
il void Inherit(re int &x)
{
  rt[++tim]=rt[x];t[tim]=t[x];ls[tim]=ls[x];rs[tim]=rs[x];x=tim;
}
il int Query(re int &x,re int l,re int r,re int k)
{
  Inherit(x);
  if(l==r) {t[x]=1;return l;}
  re int mid=l+r>>1,sz=mid-l+1-t[ls[x]],ans;
  if(k<=sz) ans=Query(ls[x],l,mid,k);
  else ans=Query(rs[x],mid+1,r,k-sz);
  t[x]=t[ls[x]]+t[rs[x]];
  return ans;
}
il ll find(re int i,re int k)
{
  re ll ans=Query(rt[i],1,tot,k),l=(i<=n?m-1:n);
  if(ans<=l) return i<=n?1ll*(i-1)*m+ans:ans*m;
  else return V[i][ans-l-1];
}
int main()
{
  n=gi();m=gi();q=gi();tot=max(n,m)+q;
  fp(i,1,n+1) rt[i]=++tim;
  fp(i,1,q)
    {
      re int x=gi(),y=gi();re ll p1,p2;
      if(y^m)
    {
      p1=find(x,y);V[n+1].pb(p1);//a new member on lie m
      p2=find(n+1,x);V[x].pb(p2);//new one ->the n_th line
    }
      else p1=find(n+1,x),V[n+1].pb(p1);
      printf("%lld\n",p1);
    }
  return 0;
}