noipd2t3列队

吉老师的题还真是难呢…

正解至今不会，只会平衡树的做法

这种用平衡树上一个点表示一段区间的题还真要做做…想起来挺难受的

建n棵平衡树表示每行的m-1个元素

再建一棵平衡树维护最后一列

中间要支持一个split操作，就是把[l,r]分成[l,x-1],x,[x+1,r]三部分，很好做

相比于bzoj上的诸多神题，这题细节不多，写起来轻松加愉快

这题要tmd动态开节点！！！一个点可以表示一段！！！查询的时候还不一定查到什么鬼地方！！！

还是Naive啊，noip前刚学完平衡树，考场上竟然不会做

这回也算是填了坑吧

Sylvia一点都不可爱

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define ll long long
#include<queue>
using namespace std;
const int maxn=3e6+;
#define l(x) son[x][0]
#define r(x) son[x][1]
int Size;
int son[maxn][],fa[maxn];
ll size[maxn],lef[maxn],rig[maxn];
struct SplayTree
{
    int rt;
    inline void pushup(int id){size[id]=size[l(id)]+size[r(id)]++rig[id]-lef[id];}
    inline void rotate(int x,int &k)
    {
        int y=fa[x],z=fa[y],L,R;
        L=(r(y)==x);R=L^;
        if(y==k)k=x;
        else son[z][son[z][]==y]=x;
        fa[son[x][R]]=y;fa[y]=x;fa[x]=z;
        son[y][L]=son[x][R];son[x][R]=y;
        pushup(y);pushup(x);
    }
    inline void Splay(int x,int &k)
    {
        while(x!=k)
        {
            int y=fa[x],z=fa[y];
            if(y!=k)
            {
                if(son[y][]==x^son[z][]==y)rotate(x,k);
                else rotate(y,k);
            }
            rotate(x,k);
        }
        pushup(x);
    }
    inline int getpos()
    {
        int x=rt;
        for(;son[x][];x=son[x][]);
        return x;
    }
    inline int addnode(ll L,ll R)
    {
        lef[++Size]=L;rig[Size]=R;size[Size]=R-L+;
        return Size;
    }
    inline void addval(ll v)
    {
        int now=addnode(v,v);
        int pos=getpos();
        son[pos][]=now;fa[now]=pos;
        Splay(now,rt);
    }
    inline int getpre(int x)
    {
        int now=son[x][];
        for(;son[now][];now=son[now][]);
        return now;
    }
    inline int getnex(int x)
    {
        int now=son[x][];
        for(;son[now][];now=son[now][]);
        return now;
    }
    inline ll split(int now,ll k)
    {
        Splay(now,rt);
        k=k+lef[now]-;
        int tmp=addnode(k+,rig[now]);
        rig[now]=k-;
        if(!son[now][])
        {
            son[now][]=tmp;
            fa[tmp]=now;
        }
        else
        {
            int pos=getnex(now);
            son[pos][]=tmp;fa[tmp]=pos;
            Splay(tmp,rt);
        }
        return k;
    }
    inline ll query(ll x)
    {
        int now=rt;ll len;
        while()
        {
            if(x<=size[son[now][]])now=son[now][];
            else
            {
                x-=size[son[now][]];
                len=rig[now]-lef[now]+;
                if(x<=len)
                {
                    if(x==)
                     {
                        ll res=lef[now];
                        lef[now]++;
                        Splay(now,rt);
                        pushup(now);
                        return res;
                     }
                     if(x==len)
                     {
                        ll res=rig[now];
                        rig[now]--;
                        Splay(now,rt);
                        pushup(now);
                        return res;
                     }
                     else return split(now,x);
                }
                x=x-(rig[now]-lef[now]+);
                now=son[now][];
            }
        }
    }
    inline void init(ll L,ll R){rt=addnode(L,R);}
}Phalanx[maxn];
ll n,m,q;
void DynaOpen()
{
    for(int i=;i<=n;i++)Phalanx[i].init(m*(i-)+,i*m-);
    Phalanx[].init(m,m);
    for(int i=;i<=n;i++)Phalanx[].addval(i*m);
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&q);
    DynaOpen();
    int x,y;ll va;
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(y==m)
        {
            printf("%lld\n",va=Phalanx[].query(x));
            Phalanx[].addval(va);
        }
        else
        {
            printf("%lld\n",va=Phalanx[x].query(y));
            Phalanx[x].addval(Phalanx[].query(x));
            Phalanx[].addval(va);
        }
    }
}