记录编号	479247	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017]列队	最终得分	100
用户昵称	lyqlyqcogs	是否通过	通过
代码语言	C++	运行时间	8.091 s
提交时间	2017-12-17 21:12:15	内存使用	494.70 MiB

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,q,c[300010][2],sum[300010]={0},it,md,p[300010]={0},P;
long long ans,la_ans,la[600000];
long long treela[3000000],la_md,la_p;
struct Tree{
    long long lt;
    long long s,rt;
    Tree(){s=0;lt=rt=-1;}
}tree[20000000];
inline long long read(){
    long long s=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch<='9'&&ch>='0'){s=s*10+ch-'0';ch=getchar();}
    return s;
}
void Build(int l,int r,int rt){
    if(tree[rt].s!=r-l+1&&l!=r){
        int mid=(l+r)>>1;
        if(tree[rt].s>mid-l+1)tree[it].s=mid-l+1;
        else tree[it].s=tree[rt].s;
        tree[rt].lt=it++;
        Build(l,mid,it-1);
        tree[it].s=tree[rt].s-tree[tree[rt].lt].s;
        tree[rt].rt=it++;
        Build(mid+1,r,it-1);
    }
}
void getans(int l,int r,int rt){
    if(l==r){
        if(tree[rt].lt!=-1)ans=tree[rt].lt;
        else ans+=l;
    }
    else{
        int mid=(l+r)>>1;
        if(tree[rt].lt==-1){
            tree[it].s=mid-l+1;
            tree[rt].lt=it++;
            tree[it].s=r-mid;
            tree[rt].rt=it++;
        }
        if(md<=tree[tree[rt].lt].s)getans(l,mid,tree[rt].lt);
        else{
            md-=tree[tree[rt].lt].s;
            getans(mid+1,r,tree[rt].rt);
        }
    }
    tree[rt].s--;
}
void insert(int l,int r,int rt){
    if(l==r)tree[rt].lt=la_ans;
    else{
        int mid=(l+r)>>1;
        if(P<=mid)insert(l,mid,tree[rt].lt);
        else insert(mid+1,r,tree[rt].rt);
    }
    tree[rt].s++;
}
void la_build(int l,int r,int rt){
    if(l==r){
        if(l<=n){treela[rt]=1;la[l]=l*m;}
        else treela[rt]=0;
    }
    else{
        int mid=(l+r)>>1;
        la_build(l,mid,rt<<1);
        la_build(mid+1,r,rt<<1|1);
        treela[rt]=treela[rt<<1]+treela[rt<<1|1];
    }
}
void la_getans(int l,int r,int rt){
    if(l==r)la_ans=la[l];
    else{
        int mid=(l+r)>>1;
        if(la_md<=treela[rt<<1]) la_getans(l,mid,rt<<1);
        else{
            la_md-=treela[rt<<1];
            la_getans(mid+1,r,rt<<1|1);
        }
    }
    treela[rt]--;
}
void la_insert(int l,int r,int rt){
    if(l==r)la[l]=ans;
    else{
        int mid=(l+r)>>1;
        if(la_p<=mid) la_insert(l,mid,rt<<1);
        else la_insert(mid+1,r,rt<<1|1);
    }
    treela[rt]++;
}
int main(){
    register int i;
    freopen("2017phalanx.in","r",stdin);
    freopen("2017phalanx.out","w",stdout);
    n=read();m=read();q=read();la_p=it=n+1;
    for(i=0;i<q;i++){
        c[i][0]=read();c[i][1]=read();
        if(c[i][1]!=m)sum[c[i][0]]++;
    }
    for(i=1;i<=n;i++){
        tree[i].s=m-1;
        Build(1,m-1+sum[i],i);
    }
    la_build(1,n+q,1);
    for(i=0;i<q;i++){
        la_md=c[i][0];
        la_getans(1,n+q,1);
        if(c[i][1]==m) ans=la_ans;
        else{
            md=c[i][1];
            ans=(long long)m*(c[i][0]-1);
            getans(1,m-1+sum[c[i][0]],c[i][0]);
            P=m+p[c[i][0]]++;
            insert(1,m-1+sum[c[i][0]],c[i][0]);
        }
        printf("%lld\n",ans);
        la_insert(1,n+q,1);
        la_p++;
    }
    return 0;
}