题解 P3960 【列队】
YoungNeal
2018-05-20 16:22:00
题解在博客[食用](http://www.cnblogs.com/YoungNeal/p/9063703.html)效果更佳哦~
## Solution
$fhq\_Treap$ [了解一下](http://www.cnblogs.com/YoungNeal/p/8977328.html)
---
### 算法部分
这题不管怎么做直接存每个人都会炸，所以我们用 $Treap$ 维护区间，即 $Treap$ 上的每个节点代表的是一个区间。
对于每行从第 $1$ 列到第 $m-1$ 列维护一个 $Treap$。
对于最后一列我们单独维护一个 $Treap$ 。
如果 $(x,y)$ 出队，要分两种情况讨论，第一种 $y=m$，即出队的人在最后一列的情况，如果不讨论的话我们在每行维护的 $Treap$ 上是找不到这个点的，因此需要分类。
对于这种情况，我们直接在最后一列的 $Treap$ 中找到第 $x$ 个人，把它 $split$ 出来，然后 $merge$ 到结尾即可。
(关于如何 $split$ 和 $merge$ 下面有讲)
第二种 $y\neq m$。
对于这种情况，我们需要在第 $x$ 行的那个 $Treap$ 中找到第 $y$ 个点，把它 $split$ 出来记为点 $a$，同时在最后一列的 $Treap$ 中找到第 $x$ 个点，同样 $split$ 出来记为点 $b$ 。
之后把点 $b$ 合并到第 $x$ 行 $Treap$ 的最后一个节点，把点 $a$ 合并到最后一列的 $Treap$ 的最后一个节点即可。
---
### 实现部分
这题 $fhq\_Treap$ 难实现的地方就在如何 $split$ 出一个不存在的节点(因为我们维护的一直是区间，而这题里 $split$ 要做的就是在一个大区间的基础上 $split$ 出两个新的小区间)
如何处理呢？
仿照一般 $fhq\_Treap$ 的 $split$ 操作，我们定义
```cpp
split(int now,int k,int &x,int &y)
```
表示在以 $now$ 为根的子树中进行分离，分离出的左子树大小为 $k$，根节点为 $x$,分离出的右子树根节点为 $y$ (我们并不能知道右子树的大小是多少)。
这时我们就要分情况讨论了：
如果 $now$ 的左子树的大小已经大于了 $k$，那么我们就不用把 $now$ 这个点拆开而是递归进入 $now$ 的左子树进行处理。
否则我们就要进行麻烦的裂点操作了。
因为要在以 $now$ 为根的子树中分出 $k$ 个，所以我们要从 $now$ 和 $now$ 的右子树里分出 $k-sze[ch[now][0]]$ 个。
这里又要分情况讨论：
如果 $now$ 这个点维护的区间大小不小于 $k$ 的话，从 $now$ 里分出大小为
$k-sze[ch[now][0]]$ 的区间即可(因为左子树已经有了 $sze[ch[now][0]]$ 那么多)。
否则就要调用
```cpp
split(ch[now][1],k-sze[ch[now][0]]-(r[now]-l[now]+1),ch[now][1],y)
```
这个意思是，把 $now$ 这个点的区间全部给了左子树还是不够，所以要进入右子树分剩下的大小为 $k-sze[ch[now][0]]-(r[now]-l[now]+1)$ 的区间。
但是实际写代码的时候不必要那么复杂的分类讨论。因为如果 $split$ 传进去的 $k$ 是非正整数的话(对应第一种情况)，那么递归会一直进入左子树，相反对于第二种情况，在分裂新节点的时候判一下就可以了，大概长这样。
```cpp
void split_new(int now,int k){
if(k>=r[now]-l[now]+1) return;
...
}
```
---
## Code
```cpp
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define N 300005
#define int long long
int root[N];
int n,m,T,tot;
int ch[N*20][2];
int l[N*20],r[N*20];
int sze[N*20],prio[N*20];
int newnode(int x,int y){
tot++;
l[tot]=x;
r[tot]=y;
sze[tot]=y-x+1;
prio[tot]=rand();
return tot;
}
void pushup(int x){
sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+r[x]-l[x]+1;
}
int merge(int x,int y){
if(!x or !y) return x+y;
if(prio[x]<prio[y]){
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
void split_new(int now,int k){//把now的大小变为k
if(k>=r[now]-l[now]+1) return;
int want=l[now]+k-1;
int nn=newnode(want+1,r[now]);
r[now]=want;
ch[now][1]=merge(nn,ch[now][1]);
pushup(now);
}
void split(int now,int k,int &x,int &y){
if(!now) x=y=0;
else{
if(sze[ch[now][0]]>=k){
y=now;
split(ch[now][0],k,x,ch[now][0]);
}
else{
split_new(now,k-sze[ch[now][0]]);
x=now;
split(ch[now][1],k-sze[ch[now][0]]-(r[now]-l[now]+1),ch[now][1],y);
}
pushup(now);
}
}
signed main(){
srand(time(0));
scanf("%lld%lld%lld",&n,&m,&T);
for(int i=1;i<=n;i++)
root[i]=newnode((i-1)*m+1,i*m-1);
for(int i=1;i<=n;i++)
root[n+1]=merge(root[n+1],newnode(i*m,i*m));
while(T--){
int a,b;
scanf("%lld%lld",&a,&b);
if(b!=m){
int x,y,z;
split(root[a],b,x,y);
split(x,b-1,x,z);
printf("%lld\n",l[z]);
int x1,y1,z1;
split(root[n+1],a,x1,y1);
split(x1,a-1,x1,z1);
root[a]=merge(x,merge(y,z1));
root[n+1]=merge(x1,merge(y1,z));
}
else{
int x,y,z;
split(root[n+1],a,x,y);
split(x,a-1,x,z);
printf("%lld\n",l[z]);
root[n+1]=merge(x,merge(y,z));
}
}
return 0;
}
```