【洛谷P3960】列队题解
题目链接
题意：
Sylvia 是一个热爱学习的女孩子。
前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。
Sylvia 所在的方阵中有 n×m 名学生，方阵的行数为 n ，列数为 m 。
为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到 n×m 编上了号码（参见后面的样例）。即：初始时，第 i 行第 j 列 的学生的编号是 (i−1)×m+j 。
然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x,y)(1≤x≤n,1≤y≤m)描述，表示第 x 行第 y 列的学生离队。
在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：
向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第 x 行第 m列。
向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第 n 行第 m列。
教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 n 行第 m 列一个空位，这时这个学生会自然地填补到这个位置。
因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。
注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。
输入格式：
输入共 q+1 行。
第 1 行包含 3 个用空格分隔的正整数 n,m,q，表示方阵大小是 n 行 m 列，一共发生了 q 次事件。
接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x,y，用一个空格分隔，表示这个离队事件中离队的学生当时排在第 x 行第 y 列。
输出格式：
按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。
样例输入：
样例输出：
时空限制：
每个测试点2s，512MB
数据范围：
n,m,q≤3×10，对于每一对(x,y)，满足1≤x≤n且1≤y≤m。
题解：
O(nq)暴力只能拿30分。
所以我们需要用数据结构来维护当前坐标为(x,y)的学生的编号是多少。
我们可以对于每一行和最后一列分别建一棵线段树，那么学生的离队、入队就对应线段树中的删除节点、插入节点的操作。其实我们并不需要真的插入和删除节点（不然就变成平衡树了），我们只需要维护节点在线段树中的前缀和即可，点在线段树中的前缀和就是点所对应的学生在方阵中的位置。
具体怎么操作呢？
每个节点的值，只有1和0两种。一个学生离队时，只需要把该学生对应的节点的值变为0，这样该节点以后的节点的前缀和都会-1。一个节点入队时，把线段树中当前最后一个节点所在位置（lastpos数组）的后一个位置的节点的权值变为1。
但是，这样会炸空间。所以我们需要动态开点！
我们用lazy来保存该区间的第一个点对应的学生的编号（注意，是学生的编号，不是区间的修改量，本题线段树没有区间修改操作）。
又有一个新问题：线段树的区间应该取多大范围呢？对于前n棵线段树，区间范围应该取1~m-1+q，对于最后一颗线段树，区间范围应该取1~n+q，因为最坏情况下，q个修改操作都在同一棵线段树上进行，而每一个修改操作都会使lastpos+1。
这样，时间复杂度O(qlogn)，动态开点也节省了大部分空间，本题就可以做了。参考代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 300001
#define maxid 15000000
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
struct segment{//动态开点线段树
int ls,rs,sum;//左子节点编号、右子节点编号、区间和
ll lazy;//初始化及存储叶子结点所代表人的编号用
segment(){
ls=rs=sum=lazy=;
}
}seg[maxid];
int n,m,q,segid=;
inline void maintain(int bh){//用子节点的信息维护该节点的信息
seg[bh].sum=seg[seg[bh].ls].sum+seg[seg[bh].rs].sum;
}
inline void build(int&bh,int L,int R,int l,int r,ll val){//初始建树
if(!bh)bh=++segid;//动态开点
if(l==L&&r==R){//区间完全覆盖
seg[bh].lazy=val;//打上lazy标记
seg[bh].sum=r-l+;//区间和
return;
}
int mid=(L+R)>>;
if(l<=mid)build(seg[bh].ls,L,mid,l,min(mid,r),val);
if(r>mid)build(seg[bh].rs,mid+,R,max(mid+,l),r,val+max(,mid+-l));
maintain(bh);
}
inline void build2(int&bh,int L,int R,int l,int r,ll val){
if(!bh)bh=++segid;
if(l==L&&r==R){
seg[bh].lazy=val;
seg[bh].sum=r-l+;
return;
}
int mid=(L+R)>>;
if(l<=mid)build2(seg[bh].ls,L,mid,l,min(mid,r),val);
if(r>mid)build2(seg[bh].rs,mid+,R,max(mid+,l),r,val+(long long)m*max(,mid+-l));//和build不同的地方
maintain(bh);
}
inline ll qup(int&bh,int L,int R,int rank){//找到排名为rank的节点所代表人的编号并更新sum
if(L==R)return seg[bh].sum=,seg[bh].lazy;//已经到叶子结点，清除该节点（即该节点的值sum=0）
int mid=(L+R)>>;
if(seg[bh].lazy){//动态开点（开bh的两个子节点）并下传标记
seg[bh].ls=++segid;
seg[bh].rs=++segid;
seg[seg[bh].ls].lazy=seg[bh].lazy;
seg[seg[bh].rs].lazy=seg[bh].lazy+mid-L+;
seg[bh].lazy=;
seg[seg[bh].ls].sum=mid-L+;
seg[seg[bh].rs].sum=R-mid;
}
ll ans;
if(rank<=seg[seg[bh].ls].sum)ans=qup(seg[bh].ls,L,mid,rank);
else ans=qup(seg[bh].rs,mid+,R,rank-seg[seg[bh].ls].sum);
maintain(bh);
return ans;
}
inline ll qup2(int&bh,int L,int R,int rank){
if(L==R)return seg[bh].sum=,seg[bh].lazy;
int mid=(L+R)>>;
if(seg[bh].lazy){
seg[bh].ls=++segid;
seg[bh].rs=++segid;
seg[seg[bh].ls].lazy=seg[bh].lazy;
seg[seg[bh].rs].lazy=seg[bh].lazy+(long long)m*(mid-L+);//和qup不同的地方
seg[bh].lazy=;
seg[seg[bh].ls].sum=mid-L+;
seg[seg[bh].rs].sum=R-mid;
}
ll ans;
if(rank<=seg[seg[bh].ls].sum)ans=qup2(seg[bh].ls,L,mid,rank);
else ans=qup2(seg[bh].rs,mid+,R,rank-seg[seg[bh].ls].sum);
maintain(bh);
return ans;
}
int lastpos[maxn];//每棵线段树最后一次插入的位置
inline void add(int&bh,int L,int R,int pos,ll val){
if(!bh)bh=++segid;//动态开点，此时不可能有lazy标记
if(L==R){//已经到叶子结点，添加节点
seg[bh].lazy=val;
seg[bh].sum=;
return;
}
int mid=(L+R)>>;
if(pos<=mid)add(seg[bh].ls,L,mid,pos,val);
else add(seg[bh].rs,mid+,R,pos,val);
maintain(bh);
}
int main(){
scanf("%d%d%d",&n,&m,&q);
segid=n+;
if(m>)for(int i=;i<=n;++i){//建立n棵行线段树
build(i,,m-+q,,m-,(long long)m*(i-)+);//保证第i棵行线段树的根的编号为i
lastpos[i]=m-;//最后一次插入的位置，下次插入就要在该位置的后一个位置插入
}
int lst=n+;//lst是最后一列的线段树的根的编号
build2(lst,,n+q,,n,m);//建立最后一列线段树
lastpos[lst]=n;
for(int i=;i<q;++i){
int x,y;
scanf("%d%d",&x,&y);
if(y<m){
ll bh=qup(x,,m-+q,y);//需要出队的人的编号
printf("%lld\n",bh);
ll bh2=qup2(lst,,n+q,x);//需要从最后一列的线段树移动到行线段树中的人的编号
add(x,,m-+q,++lastpos[x],bh2);
add(lst,,n+q,++lastpos[lst],bh);
}else{
ll bh2=qup2(lst,,n+q,x);//需要出队的人的编号
printf("%lld\n",bh2);
add(lst,,n+q,++lastpos[lst],bh2);
}
}
return ;
}