列队 权值线段树

神仙题。

一直在想如何使一行队伍整体向左移动，向上移动，没想到可以用权值线段树搞。

详细讲一下权值线段树具体实现操作。

用权值线段树维护当前行学生出列的信息，区间维护出列学生个数，并在每行开一个vector记录后面加进来的学生编号。第\(j\)列学生出列，即在这颗权值线段树上将第\(j\)列学生原来的位置\(+1\)，表示此下标位置学生出列，然后将其放进当前行的vector。查询当前行第\(j\)列学生时，我们在权值线段树上查询，像平衡树那样，参考区间已经出列学生的信息来找到还未出列的第\(j\)个学生此时的线段树下标，这里如果下标小于列数那么说明就是下标就是原列编号，否则说明当前行第\(j\)个是后面加入的学生，于是我们从vector里面找就好了。

另外，不用担心出列vector里面的学生这种情况，因为出列学生时会在权值线段树上删除了这个学生，所以查询时不会查到这个已经被删除的学生。

再看这道题本身，我们维护\(n+1\)棵权值线段树，前\(n\)棵维护前\(n\)列前\(m-1\)列的信息，第\(n+1\)棵单独维护第\(m\)列。出列时，对于第\(m\)列的点，我们直接对第\(n+1\)棵线段树操作；对于不是第\(m\)列的，我们对\(x\)行的线段树操作，再对第\(m\)列的第\(x\)行（即第\(n+1\)棵线段树）操作即可。

#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
inline int read(){
    char ch=getchar();int s=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') s=s*10+(ch^'0'), ch=getchar();
    return s;
}
int n,m,q,mxr;
#define MAXN 300003
#define MAXM MAXN*20
int tre[MAXM],sl[MAXM],sr[MAXM],cnt;
void change(int &x, int l, int r, int pos){
    if(x==0) x=++cnt;
    ++tre[x]; // 区间删除的学生个数+1
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) change(sl[x], l, mid, pos);
    else change(sr[x], mid+1, r, pos);
}
int query(int x, int l, int r, int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    int lsum=mid-l+1-tre[sl[x]]; // 左儿子区间实际存在的学生个数
    if(lsum>=k) return query(sl[x], l, mid, k);
    else return query(sr[x], mid+1, r, k-lsum);
}
int rot[MAXN];
int rot_last_col;
vector<ll> ext[MAXN+1];
inline ll del_last_col(int x){
    int pos=query(rot_last_col, 1, mxr, x); // 找到实际第x个学生的下标
    change(rot_last_col, 1, mxr, pos);
    if(pos<=n) return (ll)pos*m;
    else return ext[n+1][pos-n-1];
}
inline ll del(int x, int y){
    int pos=query(rot[x], 1, mxr, y);
    change(rot[x], 1, mxr, pos);
    if(pos<=m-1) return (ll)(x-1)*m+pos;
    else return ext[x][pos-m];
}
int main(){
    n=read(),m=read(),q=read();
    mxr=max(n,m)+q;
    while(q--) {
        int x=read(),y=read();
        if(y==m){
            ll ans=del_last_col(x); // 删除最后一列的第x行
            ext[n+1].push_back(ans); // 将(x,y)放到位置(n,m)
            printf("%lld\n", ans);
        }else{
            ll ans=del(x, y); // 删除第x行第y列
            ll ans2=del_last_col(x); // 删除最后一列的第x行
            ext[x].push_back(ans2);  // 将第x行最后一列的学生加入到第x行中
            ext[n+1].push_back(ans);  // 将(x,y)放到位置(n,m)
            printf("%lld\n", ans);
        }
    }
    return 0;
}