列队

周雨欣11J202 · 2018-11-09 08:06:08 · 个人记录

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const int N = 3e5+5,M =1e7; 
LL n,m,p,R,now;//R最长（差）M
LL rt[N],len[M],ls[M],rs[M],tot,le[N];
LL num[M];
inline void read(LL &x){
    char ch=getchar();x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
}
inline void point(LL x){
    if(x>9)point(x/10);
    putchar(x%10+'0');
}
inline LL get(LL l,LL r){
    if(now==n+1){
        if(r<=n)return r-l+1;
        if(l<=n)return n-l+1;
        return 0;
    }
    if(r<m)return r-l+1;
    if(l<m)return m-l;
    return 0;
}
inline void add(LL &k,LL p,LL w,LL l,LL r){
    if(!k){
        k=++tot;
        len[k]=get(l,r);//这一段没人离开过，是完整的，趁这时记录下实际长度 ，方便查找 （用x（题目给出）寻人）与cut （剪出），总之与add无关 
        if(l==r)num[k]=w;
    }
    len[k]++;
    if(l==r)return;
    LL mid=(l+r)>>1;
    if(p<=mid)add(ls[k],p,w,l,mid);
    else add(rs[k],p,w,mid+1,r);
}
inline LL cut(LL &k,LL p,LL l,LL r){
    if(!k){
        k=++tot;
        len[k]=get(l,r);
        if(l==r){
            if(now==n+1)num[k]=m*l;
            else num[k]=(now-1)*m+l;//人编号 
        }
    }
    len[k]--;// 相当于有一个人走了，位子虽然还在，但后面cut运算都忽略不记，
    //（再次强调add操作与实际len，cnt等等无关，就是线段树单点修改）  
    if(l==r)return num[k];//剪走 
    int mid=l+r>>1;//是len表示mid 在（1-》R）中的实际位置 
    //(r-l)/2+1   因为l!=0,r!=n开始 是[已开发的]伪区间 
    if(!ls[k]&&p<=mid-l+1||p<=len[ls[k]])return cut(ls[k],p,l,mid);//《1》r=l+1时，mid-l=0！故mid-l+1 ，《2》与p比较用mid转化为实际队列中的下标x 
    else{
        if(!ls[k])p-=mid-l+1;
        else p-=len[ls[k]];
        return cut(rs[k],p,mid+1,r);
    }
}
int main(){
    read(n),read(m),read(p);
    R=max(n,m)+p;
    LL x,y,ans;
    while(p--){
        read(x),read(y);
        if(y==m){
            now=n+1;ans=cut(rt[now],x,1,R);
        }else now=x,ans=cut(rt[now],y,1,R);
        point(ans);
        putchar('\n');
        now=n+1;add(rt[now],n+(++le[now]),ans,1,R);//（有le数组记录多出长度，直接用p（结构下标）加人） 
        if(y!=m){
            now=n+1,ans=cut(rt[now],x,1,R);
            now=x;add(rt[x],m-1+(++le[now]),ans,1,R);//由题，无论是  1-》n（行） 还是 n+1（最后一列） 只会在末尾加人 
        }   
    }
    return 0;
}
/*
2 2 3
1 1
2 2
1 2
*/