P3960 [NOIP2017 提高组] 列队， 样例1下载

#include<bits/stdc++.h>
#define int long long
using namespace std;
//快读快输开始
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x)
{
    x<0?x=-x,putchar('-'):0;
    static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
}
template<typename type,typename ...T>
inline void read(type &x,T&...y){read(x),read(y...);}
inline char read(char &ch){return ch=getchar();}
inline char write(char ch){return putchar(ch);}
template<typename type,typename ...T>
inline void write(type x,T...y){write(x),putchar(' '),write(y...),putchar('\n');}
//快读快输结束
const int N=300005;
int n,m,q,tot;
struct node{
    int s,l,r;
}tr[50*N];
int rt[N];
vector<int>v[N];
void change(int &root,int l,int r,int p)
{
    if(!root)
    {
        root=++tot;
    }
    if(l==r)
    {
        tr[root].s++;
        return;
    }
    int mid=(l+r)/2;
    if(p<=mid)
    {
        change(tr[root].l,l,mid,p);
    }
    else if(p>mid)
    {
        change(tr[root].r,mid+1,r,p);
    }
    tr[root].s=tr[tr[root].l].s+tr[tr[root].r].s;
}
int search(int root,int l,int r,int x)
{
    if(l==r)
    {
        return l;
    }
    int mid=(l+r)/2;
    int k=mid-l+1-tr[tr[root].l].s;
    if(x<=k)
    {
        search(tr[root].l,l,mid,x);
    }
    else
    {
        search(tr[root].r,mid+1,r,x-k);
    }
}
signed main()
{
    read(n,m,q);
    int maxx=n+m+q;
    for(int i=1,x,y;i<=q;i++)
    {
        read(x,y);
        if(y==m)
        {
            int t=search(rt[0],1,maxx,x);
            change(rt[0],1,maxx,t);
            int d=t*m;
            if(t>n)
            {
                d=v[0][t-n-1];
            }
            write(d);
            v[0].push_back(d);
        }
        else
        {
            int t=search(rt[x],1,maxx,y);
            change(rt[x],1,maxx,t);
            int d=(x-1)*m+t;
            if(t>=m)
            {
                d=v[x][t-m];
            }
            write(d);
            v[0].push_back(d);
            int u=search(rt[0],1,maxx,x);
            change(rt[0],1,maxx,u);
            int dd=u*m;
            if(u>n)
            {
                dd=v[0][u-n-1];
            }
            v[x].push_back(dd);
        }
        puts("");
    }
}