题意

《 $900$ 亿人一起军训》

Yurchiu 所在的方阵中有 $n \times m$ 名学生（ $n$ 行 $m$ 列）。初始时，第 $i$ 行第 $j$ 列的学生的编号是 $(i-1)\times m + j$ 。

一共发生了 $q$ 件离队事件。每一次离队事件可以用数对 $(x,y)$ （满足 $1 \le x \le n$ ，$ 1 \le y \le m$）描述，表示第 $x$ 行第 $y$ 列的学生离队。在有学生离队后，队伍中出现了一个空位。之后方阵开始：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。之后空位在第 $x$ 行第 $m$ 列。
向前看齐。这时第一行保持不动，所有学生向前填补空缺。之后空位在第 $n$ 行第 $m$ 列。

不能有两个或更多学生同时离队。离队的学生会自然地填补到第 $n$ 行第 $m$ 列。

计算每一次离队事件中，离队的同学的编号是多少。每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。

数据规模与约定

测试点编号	$n$	$m$	$q$	其他约定
$1\sim 6$	$\le 10^3$	$\le 10^3$	$\le 500$	无
$7\sim 10$	$\le 5\times 10^4$	$\le 5\times 10^4$	$\le 500$	无
$11\sim 12$	$=1$	$\le 10^5$	$\le 10^5$	所有事件 $x=1$
$13\sim 14$	$=1$	$\le 3\times 10^5$	$\le 3\times 10^5$	所有事件 $x=1$
$15\sim 16$	$\le 3\times 10^5$	$\le 3\times 10^5$	$\le 3\times 10^5$	所有事件 $x=1$
$17\sim 18$	$\le 10^5$	$\le 10^5$	$\le 10^5$	无
$19\sim 20$	$\le 3\times 10^5$	$\le 3\times 10^5$	$\le 3\times 10^5$	无

数据保证每一个事件满足 $1 \le x \le n$ ， $1 \le y \le m$ 。

点击查看题解

题解

1-6 模拟

直接按照题意模拟。时间复杂度： $O(nm)$ 。可以获得 $30$ 分。

void solve1()
{
	long long x,y;
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=m;j++)
			g[i][j]=i*m-m+j;
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",g[x][y]);
		for(long long j=y;j<=m-1;j++) swap(g[x][j],g[x][j+1]);
		for(long long j=x;j<=n-1;j++) swap(g[j][m],g[j+1][m]);
	}
}

7-10 离散化

我们发现，虽然 $n$ 和 $m$ 的范围很大，但 $q$ 很小；换言之，这个方阵中大部分行都用不到。所以我们对行进行离散。由于除了最后一列，其它列对方阵变换没有实质性影响；换言之，如果采用模拟的方式，其他列是不参与模拟过程的，所以我们只保留最后一列即可。

经过离散化，形成如下结构（~~有图片，显得这篇题解完整~~）：

然后直接按照题意模拟即可。

一个错误的离散化方法

void solve2()//错误做法 
{
	//离散化后结构：网格形 
	long long px=0,py=0;//离散化之后的矩阵的 m n 
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",x+i,y+i);//Query 
		bx[i]=x[i];by[i]=y[i];//b 数组作为 tmp 
	}
	sort(bx+1,bx+1+q);sort(by+1,by+1+q);//Begin of 离散化 
	for(long long i=1;i<=q;i++)
	{
		if(bx[i-1]!=bx[i]) px++;
		if(by[i-1]!=by[i]) py++;
		fx[bx[i]]=px;fy[by[i]]=py;//f 数组用来根据原数找到相对位置 
		ax[px]=bx[i];ay[py]=by[i];//a 数组用来根据相对位置还原原数 
	}
	if(ay[py]!=m) by[++py]=m,fy[m]=py,ay[py]=m; 
	//End of 离散化 
	for(long long i=1;i<=px;i++)
		for(long long j=1;j<=py;j++)
			g[i][j]=ax[i]*m-m+ay[j];//g 数组下标是相对位置 
	for(long long i=1;i<=q;i++)
	{
		printf("%lld\n",g[fx[x[i]]][fy[y[i]]]);
		for(long long j=fy[y[i]];j<=py-1;j++) swap(g[fx[x[i]]][j],g[fx[x[i]]][j+1]);
		for(long long j=fx[x[i]];j<=px-1;j++) swap(g[j][py],g[j+1][py]);
	}
}

错误原因：把列也离散化，其实只保留最后一列即可；将每行破坏，不能得出正确答案。

在行离散过程中，将最后一列破坏，不能得出正确答案。

一个繁琐的离散化方法

void solve3()
{
	long long px=0;//离散化之后的行数 
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",x+i,y+i);//Query 
		bx[i]=x[i];//b 数组作为 tmp 
	}
	sort(bx+1,bx+1+q);//Begin of 离散化 
	for(long long i=1;i<=q;i++)
	{
		if(bx[i-1]!=bx[i]) px++;
		fx[bx[i]]=px;//f 数组用来根据原数找到相对位置 
		ax[px]=bx[i];//a 数组用来根据相对位置还原原数 
	}
	for(long long i=1;i<=px;i++)
		for(long long j=1;j<=m-1;j++)
			G[i][j]=ax[i]*m-m+j;//G 数组下标是相对位置 
	for(long long i=1;i<=n;i++) L[i]=i*m;//L 数组是最后一列 
	for(long long i=1;i<=q;i++)
	{
		if(y[i]!=m) printf("%lld\n",G[fx[x[i]]][y[i]]);
		else printf("%lld\n",L[x[i]]);
		for(long long j=y[i];j<=m-2;j++) swap(G[fx[x[i]]][j],G[fx[x[i]]][j+1]);
		swap(G[fx[x[i]]][m-1],L[x[i]]);
		for(long long j=x[i];j<=n-1;j++) swap(L[j],L[j+1]);
	}
}

另外，我们考虑到，行与行直接不会互相影响。所以，我们不用考虑离散化后各行在数组中的位置。由此，可以得到下面的优化版代码。

void solve5()//对 solve3 的优化 行与行之间互不影响 
{
	long long px=0,x,y;
	for(long long i=1;i<=n;i++) L[i]=i*m; 
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		if(bx[x]==0) 
		{
			px++;bx[x]=px,h[px]=x;
			for(long long j=1;j<=m;j++)
				G[px][j]=x*m-m+j;
		}
		if(y!=m) printf("%lld\n",G[bx[x]][y]);
		else printf("%lld\n",L[x]);
		for(long long j=y;j<=m-2;j++) swap(G[bx[x]][j],G[bx[x]][j+1]);
		swap(G[bx[x]][m-1],L[x]);
		for(long long j=x;j<=n-1;j++) swap(L[j],L[j+1]);
	}
}

时间复杂度是 $O(qm)$ ，结合算法 1 可以得到 $50$ 分。

11-16 树状数组 + 二分

注意到此时的数据范围，对于所有询问， $x=1$ 。也就是说，只有第一行和最后一列有用（11-14 数据点本质上和 15-16 一样，故划归到 11-16）。

此时，我们可以将弯折的序列“掰直”，用一个数组维护。即，把第一行和最后一列压成一维数组。

---
  |   =>   ----- (1,2,3,6,9)
  |

也就是说，维护的数列要支持两个操作：

查询第 $x$ 个元素。
将元素移到数列最后面。

这里使用一个巧妙的方法：开一个标记数组，初始时 $1\sim n+m-1$ （末尾）都为 $1$ ，表示这个位置上有数；在发生离队事件后，相应的位置变为 $0$ ，而当前数组末尾的下一个标记变为 $1$ ，表示这个数移到末尾。

对这个数组求前缀和，其前缀和数组中的值正对应查询中的 $y$ （ $y$ 意义同题意所述），下标正对应现数列中第 $y$ 个数所在位置。

树状数组维护标记数组的前缀和；利用二分，根据标记数组前缀和，来寻找数列中第 $y$ 个数所在位置。

时间复杂度是 $O(N(\log N)^2)$ ，结合前面的算法可得到 $80$ 分。

void solve4()
{
	long long l,r,mid,Y,pos;
	for(long long i=1;i<=m;i++) a[i]=i,update(i,1);
	for(long long i=m+1;i<=m+n-1;i++) a[i]=(i-m+1)*m,update(i,1);
	for(long long i=1;i<=q;i++)
	{
		l=1,r=N2*4;pos=n+m-1+i;
		while(l<=r)
		{
            mid=(l+r)/2;
			if(query(mid)>=y[i]) Y=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%lld\n",a[Y]);
		update(Y,-1);update(pos,1);a[pos]=a[Y];a[Y]=0;
	}
}

1-20 动态开点线段树

经过动态开点，可以节省一些空间，来足以通过本题。

我们要开 $q+1$ 棵线段树：为每个询问开一个（好理解的话是每行），为最后一列开一个。

线段树中，只有叶子节点维护 data（题目中人的编号）；各节点维护的信息还有 num（这个节点维护的元素个数）。

update 操作：单点修改，修改叶子节点的 data 值。沿途中节点维护元素数加一；在行（或最后一列）的末尾插入即可。
query 操作：单点查询，查询线段树中存储的第 rank 个值。沿途中节点维护元素数减一（根据题意，询问完后接着删除）。如果递归进入左子树，仍在左子树查询第 rank 个值；如果进入右子树，则在右子树查询第 (rank $-$ 左子树元素个数) 个值。

对于每个询问，分两类讨论：

如果 $y=m$ ：
只在最后一列修改。找到第 $x$ 个数，输出并放到末尾。
否则：
先从第 $x$ 行中找到第 $y$ 个数，输出并放到最后一列末尾；把最后一列中第 $x$ 个数放到第 $x$ 行末尾。

时间复杂度是 $O(n\log n)$ 。本算法可得到 $100$ 分。

代码

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
/* 易错点：行列对应关系 
   行    列 
   n     m
   x     y
   i     j
 g[i]   [j]
*/
namespace _FullMarks
{
	/* !!注意!!
	在每次 query 以及 update 操作之后，不要忘记将“地址”赋给 root！
	因为这个，调了将近一个小时（本来可以一遍过） ！ 
	 */
	typedef long long ll;
	const ll N=300000+10,M=1000000000;
	ll cnt=0,n,m,q,root[N],last[N],end,nowAsk,nowAns;
	//对于每个询问，都开一个线段树；为最后一列专门开线段树维护。
	//last 是下一步移到队尾的位置。
	struct SGT
	{
		//线段树中叶子节点 data 是题目所述，人的编号。
		//num 指节点管理的元素个数。
		struct node{int lson,rson,num;ll data; node(){num=data=0;}}t[N*30];
		#define lson t[root].lson
		#define rson t[root].rson
		#define mid ((l+r)/2)
		ll getNum(ll l,ll r)//得到初始管理元素个数。
		{
			/* 管理区间情况（横竖皆可）。
			|----------|---------|--------|---------|
			1          l        r_1     m-1/n      r_2  */
			ll ret=0;
			if(nowAsk==0) ret=min(r,n)-l+1;
			else ret=min(r,m-1)-l+1;
			return max(ret,0ll);//最少管理 0 个元素。
		}
		ll update(ll root,ll l,ll r,ll pos,ll data)
		{
			if(root==0)
			{
				//刚刚开辟的节点，其管理元素分布必定连续。 
				root=++cnt;
				t[root].num+=getNum(l,r); 
			}
			t[root].num++;//根据题意，更新后维护元素个数加一。 
			//并且，update 的位置一定大于 m-1 或 n，这是 getNum 函数覆盖不到的。 
			if(l==r)
			{
				t[root].data=data;
				return root;
			}
			if(pos<=mid) lson=update(lson,l,mid,pos,data);
			else rson=update(rson,mid+1,r,pos,data);
			return root;
		}
		ll query(ll root,ll l,ll r,ll rank)//rank 是指查询数列第几个。
		{
			if(root==0)
			{
				//虽然有些点未创建，但根据题意，
				//仍然不能返回，因为初始返回值可以计算。 
				root=++cnt;
				t[root].num+=getNum(l,r);
				if(l==r)//这个点刚被创建，直接计算值。
				{
					if(nowAsk==0) t[root].data=l*m;
					else t[root].data=nowAsk*m-m+l;
				}
			}
			t[root].num--;//根据题意，查询后直接删除，维护数减一。 
			if(l==r)
			{
				nowAns=t[root].data;//使用它来承载答案。
				return root;//由于 query 函数可能创建节点，所以与 update 类似。 
			}
			ll Lnum;
			if(lson==0) Lnum=getNum(l,mid);//为空就现算。
			else Lnum=t[lson].num;
			if(rank<=Lnum) lson=query(lson,l,mid,rank);
			else rson=query(rson,mid+1,r,rank-Lnum);
			return root; 
		}
	}Tree;
	void yzmain()
	{
		ll x,y;
		scanf("%lld%lld%lld",&n,&m,&q);
		end=max(m,n)+q+10;
		memset(last,0,sizeof(last));
		for(int i=1;i<=q;i++)
		{
			scanf("%lld%lld",&x,&y);
			if(y==m)//直接维护最后一列 
			{
				nowAsk=0;
				root[nowAsk]=Tree.query(root[nowAsk],1,end,x);
				printf("%lld\n",nowAns);last[nowAsk]++;
				root[nowAsk]=Tree.update(root[nowAsk],1,end,last[nowAsk]+n,nowAns);
			}
			else
			{
				nowAsk=x;//先查询行。
				root[nowAsk]=Tree.query(root[nowAsk],1,end,y);
				printf("%lld\n",nowAns);
				nowAsk=0;last[nowAsk]++;//再塞到最后一列。
				root[nowAsk]=Tree.update(root[nowAsk],1,end,last[nowAsk]+n,nowAns);
				root[nowAsk]=Tree.query(root[nowAsk],1,end,x);//再把最后一列属于那一行的摘出来。
				nowAsk=x;last[nowAsk]++;//最后塞到那一行。 
				root[nowAsk]=Tree.update(root[nowAsk],1,end,last[nowAsk]+m-1,nowAns);
			}
		}
		return;
	}
}
namespace _yz
{
	const long long N1=1000+10,N2=300000+10,Q1=500+10,N3=50000+10,Q2=300000+10;
	long long n,m,q;//基本变量定义
	long long g[N1][N1];//solve1 2 共用 
	long long a[N2*4],t[N2*4];//solve4 使用 
	long long bx[Q1],fx[N3],ax[Q1];//solve2 3 共用 
	long long x[Q2],y[Q2];//solve2 3 共用，判断特殊点 
	//long long by[Q1],fy[N3],ay[Q1]; //solve2 错误做法 
	long long G[Q1][N3],L[N3];//solve3 使用
	
	long long lb(long long x){return x&-x;}
	long long query(long long x){long long ret=0;while(x>=1)ret+=t[x],x-=lb(x);return ret;}
	void update(long long x,long long y){while(x<=N2*4)t[x]+=y,x+=lb(x);}//solve4 使用 
	void solve1()
	{
		long long x,y;
		for(long long i=1;i<=n;i++)
			for(long long j=1;j<=m;j++)
				g[i][j]=i*m-m+j;
		for(long long i=1;i<=q;i++)
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",g[x][y]);
			for(long long j=y;j<=m-1;j++) swap(g[x][j],g[x][j+1]);
			for(long long j=x;j<=n-1;j++) swap(g[j][m],g[j+1][m]);
		}
	}
	void solve2()//错误做法 
	{
		/*//离散化后结构：网格形 
		long long px=0,py=0;//离散化之后的矩阵的 m n 
		for(long long i=1;i<=q;i++)
		{
			scanf("%lld%lld",x+i,y+i);//Query 
			bx[i]=x[i];by[i]=y[i];//b 数组作为 tmp 
		}
		sort(bx+1,bx+1+q);sort(by+1,by+1+q);//Begin of 离散化 
		for(long long i=1;i<=q;i++)
		{
			if(bx[i-1]!=bx[i]) px++;
			if(by[i-1]!=by[i]) py++;
			fx[bx[i]]=px;fy[by[i]]=py;//f 数组用来根据原数找到相对位置 
			ax[px]=bx[i];ay[py]=by[i];//a 数组用来根据相对位置还原原数 
		}
		if(ay[py]!=m) by[++py]=m,fy[m]=py,ay[py]=m; 
		//End of 离散化 
		for(long long i=1;i<=px;i++)
			for(long long j=1;j<=py;j++)
				g[i][j]=ax[i]*m-m+ay[j];//g 数组下标是相对位置 
		for(long long i=1;i<=q;i++)
		{
			printf("%lld\n",g[fx[x[i]]][fy[y[i]]]);
			for(long long j=fy[y[i]];j<=py-1;j++) swap(g[fx[x[i]]][j],g[fx[x[i]]][j+1]);
			for(long long j=fx[x[i]];j<=px-1;j++) swap(g[j][py],g[j+1][py]);
		}*/
	}
	void solve3()
	{
		/* 离散化后结构：
		    -------------- |
		                   |
			-------------- |
			-------------- |
		*/ 
		long long px=0;//离散化之后的行数 
		for(long long i=1;i<=q;i++)
		{
			scanf("%lld%lld",x+i,y+i);//Query 
			bx[i]=x[i];//b 数组作为 tmp 
		}
		sort(bx+1,bx+1+q);//Begin of 离散化 
		for(long long i=1;i<=q;i++)
		{
			if(bx[i-1]!=bx[i]) px++;
			fx[bx[i]]=px;//f 数组用来根据原数找到相对位置 
			ax[px]=bx[i];//a 数组用来根据相对位置还原原数 
		}
		for(long long i=1;i<=px;i++)
			for(long long j=1;j<=m-1;j++)
				G[i][j]=ax[i]*m-m+j;//G 数组下标是相对位置 
		for(long long i=1;i<=n;i++) L[i]=i*m;//L 数组是最后一列 
		for(long long i=1;i<=q;i++)
		{
			if(y[i]!=m) printf("%lld\n",G[fx[x[i]]][y[i]]);
			else printf("%lld\n",L[x[i]]);
			for(long long j=y[i];j<=m-2;j++) swap(G[fx[x[i]]][j],G[fx[x[i]]][j+1]);
			swap(G[fx[x[i]]][m-1],L[x[i]]);
			for(long long j=x[i];j<=n-1;j++) swap(L[j],L[j+1]);
		}
	}
	void solve4()
	{
		long long l,r,mid,Y,pos;
		for(long long i=1;i<=m;i++) a[i]=i,update(i,1);
		for(long long i=m+1;i<=m+n-1;i++) a[i]=(i-m+1)*m,update(i,1);
		for(long long i=1;i<=q;i++)
		{
			l=1,r=N2*4;pos=n+m-1+i;
			while(l<=r)
			{
                mid=(l+r)/2;
				if(query(mid)>=y[i]) Y=mid,r=mid-1;
				else l=mid+1;
			}
			printf("%lld\n",a[Y]);
			update(Y,-1);update(pos,1);a[pos]=a[Y];a[Y]=0;
		}
	}
	void yzmain()
	{
		long long cnt=0;
		scanf("%lld%lld%lld",&n,&m,&q);
		if(n<=1000&&m<=1000&&q<=500) solve1();
		else if(n<=50000&&m<=50000&&q<=500) solve3();
		else{
			for(long long i=1;i<=q;i++)
			{
				scanf("%lld%lld",x+i,y+i);
				if(x[i]==1) cnt++;
			}
			if(cnt==q) solve4();
			else printf("zzy AK IOI!");//zzy 这个大佬非常强！
		}
   		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_FullMarks::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/cbb35b52db0c/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 二分模拟离散化树状数组线段树

最后更新：2023-08-21, 23:18:20

By Yurchiu.

P3960 [NOIP2017 提高组] 列队

题意

数据规模与约定

题解

1-6 模拟

7-10 离散化

11-16 树状数组 + 二分

1-20 动态开点线段树

代码