lp3960 NOIP2018 列队

我没有脸把这篇文章称作是「我」的题解。
难度非常的大。
说实话根本不知道怎么写，也无法理解。
再一次感受到人和巨神的区别。

「人跟人之间是有差距的。」

实在是无法理解，所以只能抄小粉兔的题解了。
可能等到我的能力有提升了之后才能理解这道题的正解吧。
话说有个sm打成了rt卡了我半天。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lwbt(_A) ((_A)&(-(_A)))


int q,loc[300005];
long long n,m,X[300005],Y[300005],ans[300005],arr[900005];
int len[300005],len2[300005],h[300005],tr[900005];
inline void add(int *_H,int _L,int _X,int _A){
    while(_X<=_L){
        _H[_X]+=_A;
        _X+=lwbt(_X);
    }
}
inline bool cmp(const int &_A,const int &_B){
    return (X[_A]==X[_B])?(_A<_B):(X[_A]<X[_B]);
}
inline int srch(int *_H,int _L,int _X){
    int l=1,r,mid,sm,rt;
    while((l<=_L)&&(_H[l]<_X)){
        l<<=1,rt=l;
    }
    r=l;
    sm=_H[l>>=1];
    while(l+1<r){
        mid=(l+r)>>1;
        if(mid>_L||_H[mid]+sm>=_X){
            r=mid,rt=mid;
        }else{
            l=mid,sm+=_H[l];
        }
    }
    rt=r;
    return rt;
}
int st[300005],tp=0;
void init(){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=q;++i){
        scanf("%lld%lld",&X[i],&Y[i]);
        loc[i]=i;
    }
    sort(loc+1,loc+1+q,cmp);
    for(int i=1;i<m;++i){
        add(tr,m-1,i,1);
    }
    for(int i=1;i<=n;++i){
        len[i]=m-1;
    }
    for(int i=1;i<=q;++i){
        if(X[loc[i-1]]!=X[loc[i]]){
            while(tp){
                add(tr,m-1,st[tp--],1);
            }
        }
        if(Y[loc[i]]>len[X[loc[i]]]){
            continue;
        }
        int pos=srch(tr,m-1,Y[loc[i]]);
        ans[loc[i]]=(X[loc[i]]-1)*m+pos;
        add(tr,m-1,pos,-1);
        st[++tp]=pos;
        --len[X[loc[i]]];
    }
    int it=0;
    for(int i=1;i<=n;++i){
        while(it<=q&&X[loc[it]]<i){
            ++it;
        }
        h[i]=it-1;
    }
    h[n+1]=q;
    memset(tr,0,sizeof(tr));
    for(int i=1;i<=n;++i){
        len[i]=0,len2[i]=m-1;
    }
    len[n+1]=n;
    for(int i=1;i<=n;++i){
        add(tr+h[n+1],n+q,i,1);
        arr[q+i]=i*m;
    }
    for(int i=1;i<=q;++i){
        if(ans[i]){
            int pos=srch(tr+h[n+1],n+q,X[i]);
            add(tr+h[n+1],n+q,pos,-1);
            add(tr+h[n+1],n+q,++len[n+1],1);
            arr[h[n+1]+len[n+1]]=ans[i];
            add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);
            arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];
            --len2[X[i]];
        }else{
            int pos=srch(tr+h[n+1],n+q,X[i]);
            add(tr+h[n+1],n+q,pos,-1);
            add(tr+h[n+1],n+q,++len[n+1],1);
            if(Y[i]!=m){
                int pos2=srch(tr+h[X[i]],h[X[i]+1]-h[X[i]],Y[i]-len2[X[i]]);
                add(tr+h[X[i]],h[X[i]+1]-h[X[i]],pos2,-1);
                ans[i]=arr[h[X[i]]+pos2];
                add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);
                arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];
            }else{
                ans[i]=arr[h[n+1]+pos];
            }
            arr[h[n+1]+len[n+1]]=ans[i];
        }
    }
    for(int i=1;i<=q;++i){
        printf("%lld\n",ans[i]);
    }
} 
int main(){
    init();
    return 0;
}