题解：P3960 [NOIP 2017 提高组] 列队

· · 题解

题目大意

给一个 n 行 m 列的方阵，并予以行列上的维护，每次变动会对指定行列坐标进行离队和补位两种变化，并输出离队人员编号。

思路

不难发现，题目数据 1\le n,m,q\le 3\times 10^5 非常大，很明显不能直接存储，考虑到动态开点。

因为出队时变动的总是影响到最后一行，所以我们可以用动态开点线段树来维护最后一行的数。

其次，我们可以观察到每次出队人员的变动，本质上是行列上人数的变动，根据查询的人数情况，即可判断出队人的编号。

分类讨论

当 y = m 时，我们不需要执行向左看齐的指示，只需维护第 m 列的变化即可。

而当 y \ne m 时，我们通过记录修改次数，对新节点给予编号并更新，就完成了维护。

#include<bits/stdc++.h>
#define int long long
using namespace std;//要开long long我这里直接define了 
const int N=6e5+5,M=2e7+5;
//写线段树数组要开大，防止RE 
struct STree{
    int l,r;
    int sz,id;//子树大小和节点编号 
}t[M];
int n,m,q,rt[N],op[N],cnt;
//分别指行数，列数，询问次数，各树深度，修改次数，编号的增量 
int zzz;
inline void newnode(int &p,int l,int r,bool op){
    p=++cnt;
    t[p].sz=!op?max(0LL,min(n,r)-l+1):max(0LL,min(m-1,r)-l+1);
    t[p].id=!op?(l*m):((zzz-1)*m+l);
}//建一个新节点并更新其子树和编号 
inline int find(int &p,int l,int r,int pos,bool op){
    if (!p) newnode(p,l,r,op);
    --t[p].sz;
    if (l==r) return t[p].id;
    int mid=l+r>>1;
    if (!t[p].l) newnode(t[p].l,l,mid,op);
    if (pos<=t[t[p].l].sz) return find(t[p].l,l,mid,pos,op);
    else return find(t[p].r,mid+1,r,pos-t[t[p].l].sz,op);
}//查找编号 
inline void update(int &p,int l,int r,int pos,int v,bool op){
    if (!p) newnode(p,l,r,op);
    ++t[p].sz;
    if (l==r){
        t[p].id=v;
        return ;
    }
    int mid=l+r>>1;
    if (pos<=mid) update(t[p].l,l,mid,pos,v,op);
    else update(t[p].r,mid+1,r,pos,v,op);
}//更新编号 
signed main(){
    cin>>n>>m>>q;
    int len=max(n,m)+q;//因为动态开点，所以要留够空间 
    for (int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;
        if (y==m){
            int ans=find(rt[n+1],1,len,x,0);
            printf("%lld\n",ans);
            ++op[n+1];//更新操作次数 
            update(rt[n+1],1,len,n+op[n+1],ans,0);
        }else{
            zzz=x;
            int ans=find(rt[x],1,len,y,1);
            int ans2=find(rt[n+1],1,len,x,0);
            printf("%lld\n",ans);
            ++op[x];++op[n+1];
            update(rt[x],1,len,m+op[x]-1,ans2,1);
            update(rt[n+1],1,len,n+op[n+1],ans,0);
        }
    }
    return 0;
}