[Noip2017]列队

一.前言

咱高一是不是也要军训啊，害怕 qwq……题目链接

二.思路

这篇题解使用的是平衡树（FHQ），树状数组不会写也……

首先通过简单的模拟/手玩可以大概的知道，对于位置 ((x,y))，移动它会影响的只有 ((x,y+1)) 到 ((x,m)) 全部左移，以及 ((x+1,m)) 到 ((n,m)) 全部上移，最后在右下角插回去。

观察到 11~16 的测试点给的是全部 (x=1)，从局部入手获得灵感。在这种情况下，只需要维护第一行和最后一列就行。对于第一行，操作一共有两个：删除第 k 个数，在末尾插入一个数 u。具体的来说，若是 ((1,i)) 离开，那么对于第一行会删掉第 i 个数，在最后插入 ((2,m)),对于最后一列会删掉第 1 个数，在末尾插入 ((1,i))

从中我们可以找到几个共同点：

都是删掉处在位置 k 的一个数
都是在末尾插入一个数

这里若是魔改一下，改成对于行只维护 1~m-1 就会方便很多。此时同时对第一行与最后一列进行维护就可以了。不失一般性，将 1 改成 x ，对于每一行都维护就行。

这里的维护我们需要用到平衡树（杀鸡用牛刀qwq），接下来只是按我笨拙的想法讲一下原理，不是真正的算法，有点套用替罪羊的建树思想，手中已有一个数列，把他拉成一个平衡树……见图

此时（虽然不怎么像树），但是通过中序遍历是可以将整个数组都找到。在这个时候，给每个点一个随机值，使得在不违背遍历顺序的基础上以这个随机值进行旋转。见图。

（彩色的是随机值）这样中序遍历的顺序还是一样的（大概）但是很有效的将树给"压扁"了，使得每次的查询时间大幅缩减。对于每个点维护一个 (size) 表示子树大小，就能快速找到第 k 个数了。

然后再说如何基于 FHQ 来操作，FHQ 的基操 merge 与 split 是重点，但是也不难（不会的先学了来）。merge的时候就按照随机值merge就好，给出代码。

int merge(int x,int y){//以 y 为根的子树要比 x 后访问
	if(!x||!y)return x+y;
	if(rad[x]<rad[y]){//按随机值,这里规则可以随便搞其实hhhh都可以A
		ch[x][1]=merge(ch[x][1],y);
		update(x);//维护size
		return x;
	}
	else {
		ch[y][0]=merge(x,ch[y][0]);
		update(y);
		return y;
	}
}

然后这题的split稍稍有点复杂……首先由数据规模可以得出两个结论：

每个点都开，空间开不起
由于操作数远小于点数，会有一大片是连续的

于是我们可以选择将连续的看作是一个点，记录这个点的长度（总共包括几个点），以及开头的值（就可以计算出所有值），当这个点中的其中一个位置需要操作时，把这个点撕开成该位置前与后再插回去就行。

于是 split 要分出三棵树：在 k 位置之前的，（包含）k 位置（可能是一个点，也可能是连续一大片），k位置之后。给出代码。

void split(int x,int k,int &a,int &b,int &c){
	if(!x)a=b=c=0;
	else{
		if(size[ch[x][0]]>=k)c=x,split(ch[x][0],k,a,b,ch[x][0]);
        //就在左子树里面，于是进左子树找，归还一个只留>k的部分的左子树
		else{
			k-=size[ch[x][0]];//直接排除左子树，减去消耗
			if(k<=len[x]){//正好就是该节点本身
				b=x;
				a=ch[x][0];
				c=ch[x][1];
				ch[x][0]=ch[x][1]=0;
			}
			else{//进右子树寻找，还一个只有<k 的右子树
				a=x;
				k-=len[x];//减去消耗
				split(ch[x][1],k,ch[x][1],b,c);
			}
		}
		update(x);
	}
}

剩下就是主体操作，要注意操作第二维为 m 的情况，特判一下。代码会详细解释

for(int i=1;i<=n;++i){
		root[i]=add(1LL*(i-1)*m+1,m-1);//直接插入一行
		root[0]=merge(root[0],add(1LL*i*m,1));//维护一下最后一列
	}
	for(int i=1,x,y;i<=q;++i){
		x=read();y=read();
		if(y==m){//特判
			int a,b,c;
			split(root[0],x,a,b,c);//取出来
			printf("%lld
",start[b]);
			root[0]=merge(merge(a,c),b);//塞在最后
		}
		else{
			int a,b,c;
			split(root[0],x,a,b,c);//在最后一列取出来
			root[0]=merge(a,c);//合并了
			root[x]=merge(root[x],b);//反手先塞进去
			split(root[x],y,a,b,c);//取出要输出的那个
			y-=size[a];//因为有可能取出来连续的一串，需要知道是这一串的第几个
			printf("%lld
",start[b]+y-1);//输出了
			root[0]=merge(root[0],add(start[b]+y-1,1));//塞进最后一列末尾
			root[x]=
			merge(merge(a,merge(add(start[b],y-1),add(start[b]+y,len[b]-y))),c);
			//撕开成两半，塞进去
        }
	}