2017提高组-列队

这个题目对一个初入noip的童鞋来说很烧脑呢，因为对线段树并不是很熟悉，所以在做这个题目之前需要先学习几个知识点：

1. 线段树

2. 权值线段树

3. 主席树,可持久化线段树

4. 可持久化数组

经过对以上几个知识点，尤其是权值线段树和主席树的学习，才能理解如何动态建立多棵线段树，如何去找区间第K大的值。

然后才能慢慢理解这道题的做法，很多巧妙的思想是自己无论如何也想不出来的。还是佩服这些烧脑的大仙们。。。

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int N=3e5+5;
const int M=1e7+2;
ll n,m,q;
struct node{
    int ls,rs; //存储左右子树根节点的编号 
    int sz;    //存储的是当前的有效位数 
    ll val;    //存储的是队员的编号，只对 l==r,叶子节点有效 
}t[M];
int id,tot;    //动态开点 
int rt[N];     //存储n+1棵线段树的根节点编号 
ll now;        //当前操作的线段树编号 
int cur[N];    //第i棵线段树当前要更新的点的编号 
int up;

//如果有点还没有编号，说明当前没有人离队，这部分是完整的r-l+1个有效位 
//我们就直接返回这个个数就行了 
int get(int l,int 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;
}

//查询x的第c个数，离队 
ll query(int &x,int l,int r,int c){
	//编号 
    if(!x){
        x=++tot;
        t[x].sz=get(l,r);
        if(l==r){
            if(now==n+1) t[x].val=l*m;
            else t[x].val=(now-1)*m+l;
        }
    }
    //个数-1，离队 
    t[x].sz--;
    if(l==r) return t[x].val;
    if((!t[x].ls&&c<=get(l,mid))||c<=t[t[x].ls].sz) return query(t[x].ls,l,mid,c);
    else{
        if(!t[x].ls) c-=get(l,mid);
        else c-=t[t[x].ls].sz;
        return query(t[x].rs,mid+1,r,c);
    }
}

//x入队 ,位置是to,编号是d 
void upda(int &x,int l,int r,int to,ll d){
    if(!x){
        x=++tot;
        t[x].sz=get(l,r);
        if(l==r){
            t[x].val=d;
        }
    }
    //入队，个数+1 
    t[x].sz++;
    if(l==r) return;
    if(to<=mid) return upda(t[x].ls,l,mid,to,d);
    else return upda(t[x].rs,mid+1,r,to,d);
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&q);
    int x,y;
    ll ans;
    up=max(n,m)+q;
    while(q--){
        scanf("%d%d",&x,&y);
        //如果是第m列离队，则查询第n+1棵线段树的第x个数 
        if(y==m) now=n+1,ans=query(rt[now],1,up,x);
        //否则，查询第x个线段树的第y个数 
        else now=x,ans=query(rt[now],1,up,y);
        printf("%lld\n",ans);
        
        //第n+1棵线段树增加一个数，在 n+(++cur[now]) 位置
		//这个位置是新的有效位 
        now=n+1;
        upda(rt[now],1,up,n+(++cur[now]),ans);
        if(y!=m){
            now=n+1;
            //取出n+1线段树的第x个数 
            ans=query(rt[now],1,up,x);
            now=x;
            //放入第x个线段树的 m-1+(++cur[now] 位置 
            upda(rt[now],1,up,m-1+(++cur[now]),ans);
        }
    }
    return 0;
}

代码参考：https://www.cnblogs.com/Miracevin/p/9582412.html