列队[noip2017]

#include<bits/stdc++.h>
#define re return
#define LL long long
#define inc(i,l,r) for(LL i=l;i<=r;++i)

using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)f=1;
    x=c^48;
    while((c=getchar())>=‘0‘&&c<=‘9‘)x=x*10+(c^48);
    if(f)x=-x;
}

const int maxn=3000000;
LL n,m,tot,cnt,Q;
int fa[maxn],son[maxn][2];
LL size[maxn],ll[maxn],rr[maxn];

/*此题区间左闭右开*/
struct Splay
{
    int rt;
    //建新点 
    inline int New_point(LL l,LL r)
    {
        ++cnt;
        fa[cnt]=son[cnt][0]=son[cnt][1]=0;
        ll[cnt]=l;rr[cnt]=r;size[cnt]=r-l;
        re cnt;
    }
    //saply常规操作
    inline int chk(int x){re son[fa[x]][1]==x;}
    inline void pushup(int x)
    {
        size[x]=size[son[x][0]]+size[son[x][1]]+rr[x]-ll[x];
    } 
    
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y],f=chk(x),w=son[x][f^1];
        son[z][chk(y)]=x;fa[x]=z;
        son[x][f^1]=y;fa[y]=x;
        son[y][f]=w;fa[w]=y;
        pushup(y);
        pushup(x);
    }
    
    inline void splay(int x,int goal=0)
    {
        while(fa[x]!=goal)
        {
            int y=fa[x],z=fa[y];
            if(z!=goal)
            chk(x)==chk(y)?rotate(y):rotate(x);
            rotate(x);
        }
        if(!goal)rt=x;
    }
    
    //动态开点平衡树 (将n多操作合二为一） 

    //你从未见过的船新操作，动态开点
    //将前k个点放入原根，后面新开节点 
    inline LL Split_point(int u,LL k)
    {
        k+=ll[u];
        int y=New_point(k,rr[u]);
        rr[u]=k;
        if(!son[u][1])
            fa[son[u][1]=y]=u;
        else 
        {
            int t=son[u][1];
            while(son[t][0])t=son[t][0];
            fa[son[t][0]=y]=t;
            while(t!=u)pushup(t),t=fa[t];
        }
        splay(y);
        re y;
    } 
    
    //找出第K大点并弹出 
     LL Pop_kth(LL k)
    {
        int u=rt;
        while(2333)
        {
            int y=son[u][0];
            if(size[y]>=k)u=y;
            else 
            {
                k-=size[y];
                if(rr[u]-ll[u]<k)k=k-(rr[u]-ll[u]),u=son[u][1];
                else 
                {
                    if(k!=rr[u]-ll[u])Split_point(u,k);
                    if(k!=1)u=Split_point(u,k-1);
                    break;
                } 
            }
        }
        
        splay(u);
        fa[son[u][0]]=fa[son[u][1]]=0;
        if(!son[u][0])
        {
            rt=son[u][1];
        }
        else
        {
            int t=son[u][0];
            while(son[t][1])t=son[t][1];
            splay(t);
            rt=t;
            fa[son[t][1]=son[u][1]]=t;
            pushup(t);
        }
        re ll[u]; 
    }
    
    
    //找到最后，并放进新数 
    inline void Push_back(LL x)
    {
        int p=New_point(x,x+1);
        if(!rt)    rt=p;
        else
        {
            int u=rt;
            while(son[u][1])
                u=son[u][1];
            splay(u); 
            son[fa[p]=u][1]=p;
            pushup(u);
        }
    }
    
}s[maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    freopen("testdata.in","r",stdin);
    LL x,y,p;
    
    rd(n),rd(m),rd(Q);
    
    //建树 
    inc(i,1,n) s[i].rt=s[i].New_point((i-1)*m+1,i*m);
    s[0].rt=s[0].New_point(m,m+1);
    inc(i,2,n)
        s[0].Push_back(i*m);
    
    inc(i,1,Q)
    {
        rd(x),rd(y);
        s[x].Push_back(s[0].Pop_kth(x));
        printf("%lld\n",p=s[x].Pop_kth(y));    
        s[0].Push_back(p);
    }  
    
    re 0;
}