LOJ2319「NOIP2017」列队

原题链接：https://loj.ac/problem/2319

列队

题目描述

Sylvia 是一个热爱学习的女孩子。

前段时间， Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。 Sylvia所在的方阵中有$n \times m$n×m名学生，方阵的行数为$n$n，列数为 $m$m。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从$1$1到$n \times m$n×m编上了号码（参见后面的样例）。即：初始时，第$i$i行第$j$j列的学生的编号是$(i − 1) \times m + j$(i−1)×m+j。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了$q$q件这样的离队事件。每一次离队事件可以用数对$(x, y) (1\le x\le n, 1\le y\le m)$(x,y)(1≤x≤n,1≤y≤m)描述， 表示第$x$x行第$y$y列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第$x$x行第$m$m列。

向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第$n$n行第$m$m列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 $n$n行第$m$m列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。

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

输入格式

输入共$q+1$q+1行。

第$1$1行包含$3$3个用空格分隔的正整数$n, m, q$n,m,q，表示方阵大小是$n$n行 $m$m列，一共发生了$q$q次事件。

接下来$q$q行按照事件发生顺序描述了$q$q件事件。每一行是两个整数$x, y$x,y， 用一个空格分隔， 表示这个离队事件中离队的学生当时排在第$x$x行第$y$y列。

输出格式

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

样例

样例输入

2 2 3
1 1
2 2
1 2

样例输出

1
1
4

样例解释

列队的过程如上图所示，每一行描述了一个事件。

在第一个事件中，编号为$1$1的同学离队，这时空位在第一行第一列。接着所有同学向左标齐，这时编号为$2$2的同学向左移动一步，空位移动到第一行第二列。然后所有同学向上标齐，这时编号为$4$4的同学向上一步，这时空位移动到第二行第二列。最后编号为$1$1的同学返回填补到空位中。

数据范围与提示

测试点编号	$n$n	$m$m	$q$q	其他约定
$1,2,3,4,5,6$1,2,3,4,5,6	$\le 1000$≤1000	$\le 1000$≤1000	$\le 500$≤500	无
$7,8,9,10$7,8,9,10	$\le 5 \times 10^{4}$≤5×104	$\le 5 \times 10^{4}$≤5×104	$\le 500$≤500	无
$11,12$11,12	$=1$=1	$\le 10^{5}$≤105	$\le 10^5$≤105	所有事件$x=1$x=1
$13,14$13,14	$=1$=1	$\le 3\times 10^{5}$≤3×105	$\le 3\times 10^5$≤3×105	所有事件$x=1$x=1
$15,16$15,16	$\le 3\times 10^5$≤3×105	$\le 3\times 10^{5}$≤3×105	$\le 3\times 10^5$≤3×105	所有事件$x=1$x=1
$17,18$17,18	$\le 10^5$≤105	$\le 10^{5}$≤105	$\le 10^5$≤105	无
$17,18$17,18	$\le 3\times 10^5$≤3×105	$\le 3\times 10^{5}$≤3×105	$\le 3\times 10^5$≤3×105	无

数据保证每一个事件满足$1\leq x \leq n,1\leq y \leq m$1≤x≤n,1≤y≤m。

题解

发现$markdown$markdown居然不资瓷合并单元格，表格一下就不优美了。。。

发现每次$(x,y)$(x,y)的离队都只会影响第$x$x行和最后一列，包含两个操作：弹出第$k$k个，将元素放到队尾。

于是就有了暴力的做法：对于每一行开一棵$\mathcal{Splay}$Splay，最后一列再单独开一棵，就能自然地完成上述两个操作，然而总共有$O(nm)$O(nm)个点，显然凉凉~

仔细观察，可以发现有一些编号连续的点始终在一起，这些点对应的节点可以合并为一个节点，进一步讲，我们可以先将所有该$\mathcal{Splay}$Splay里的连续节点全部合并，在弹出节点属于合并节点时再把节点拆开，相当于动态开点，这样点数就是$O(q)$O(q)的，总复杂度$O(q\log q)$O(qlogq)。

$\mathcal{Splay}$Splay题真的巨考细节。。。简单说一下：

感觉先在$\mathcal{Splay}$Splay里插入两个哨兵节点是个很好的技巧，避免了与前驱后继相关的操作中繁琐的特判，不会莫名$\mathcal{RE}$RE。

拆点比较细节，有下面几种情况：
1.$le[v]=ri[v]$le[v]=ri[v]，已经不需要拆了，直接删掉；
2.$le[v]=pos||pos==ri[v]$le[v]=pos∣∣pos==ri[v]查询位置在当前节点表示区间的端点上，直接修改节点信息即可；
3.$le[v]&lt;pos&lt;ri[v]$le[v]<pos<ri[v]，将原来节点的信息修改为$[le[v],pos-1]$[le[v],pos−1]，新增一个节点$[pos+1,ri[v]]$[pos+1,ri[v]]，插入到$[le[v],pos-1]$[le[v],pos−1]的后继的左儿子上。

放到队尾的操作就是把该点插入到右哨兵的前驱的左儿子上。

然后，你就迎来了愉快的$\mathcal{Debug}$Debug生活。

代码

#include<bits/stdc++.h> 
#define ll long long
#define ls son[v][0]
#define rs son[v][1]
using namespace std;
const int M=2e7+5;
ll n,m,q,le[M],ri[M],siz[M];;
int dad[M],son[M][2],tot;
struct sd{
	int root,mx,mn;
	int _new(ll L,ll R){return le[++tot]=L,ri[tot]=R,siz[tot]=R-L+1,tot;}
	void up(int v){siz[v]=siz[ls]+siz[rs]+ri[v]-le[v]+1;}
	void spin(int v){int f=dad[v],ff=dad[f],k=son[f][1]==v,w=son[v][!k];son[ff][son[ff][1]==f]=v,son[v][!k]=f,son[f][k]=w;dad[w]=f,dad[f]=v,dad[v]=ff;up(f);}
	void splay(int v,int to){for(int f,ff;dad[v]!=to;spin(v)){f=dad[v],ff=dad[f];if(ff!=to)spin((son[f][0]==v)^(son[ff][0]==f)?v:f);}if(!to)root=v;up(v);}
	int nxt(int v,int p){splay(v,0);for(v=son[v][p];son[v][!p];v=son[v][!p]);return v;}
	void del(int v){int up=nxt(v,1),low=nxt(v,0);splay(low,0),splay(up,low);son[up][0]=0;splay(up,0);}
	void push(ll L,ll R){int v=_new(L,R),low=nxt(mx,0);son[low][1]=v,dad[v]=low;splay(v,0);}
	ll pop(ll pos)
	{
		int v=root;
		for(pos++;;)
		{
			if(pos>siz[ls]+ri[v]-le[v]+1)pos-=siz[ls]+ri[v]-le[v]+1,v=rs;
			else if(pos<=siz[ls])v=ls;
			else break;
		}
		pos+=le[v]-siz[ls]-1;
		if(le[v]==ri[v])return del(v),pos;
		if(le[v]==pos)return ++le[v],splay(v,0),pos;
		if(pos==ri[v])return --ri[v],splay(v,0),pos;
		int upp=nxt(v,1);_new(pos+1,ri[v]),ri[v]=pos-1,up(v);
		return dad[tot]=upp,son[upp][0]=tot,splay(tot,0),pos;
	}
	void reset(ll L,ll R){mn=_new(L,L),mx=_new(R,R),dad[mx]=mn,son[mn][1]=mx;splay(mx,0);}
}que[300005];
void in(){scanf("%lld%lld%lld",&n,&m,&q);}
void ac()
{
	ll val;
	que[0].reset(0,n*m+m);
	for(int i=1;i<=n;++i)que[i].reset(i*m-m,i*m),que[i].push((i-1)*m+1,i*m-1),que[0].push(i*m,i*m);
	for(int i=1,x,y;i<=q;++i)scanf("%d%d",&x,&y),val=que[0].pop(x),que[x].push(val,val),val=que[x].pop(y),que[0].push(val,val),printf("%lld\n",val);
}
int main(){in(),ac();}