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

题目大意

给一个

n

行

m

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

思路

不难发现，题目数据

1\le n,m,q\le 3\times 10^5

非常大，很明显不能直接存储，考虑到动态开点。

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

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

分类讨论

当

y = m

时，我们不需要执行向左看齐的指示，只需维护第

m

列的变化即可。

而当

y \ne m

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

CPP

#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;
}

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

文章操作

题目大意

思路

分类讨论

相关推荐

评论

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