NOIP2017D2T3

题解： NOIP2017 D2 T3 列队

题目链接： 列队

题目描述：

有一个 $n$ 行 $m$ 列的方阵，初始时第 $i$ 行第 $j$ 列的学生编号为 $(i-1)*m+j$ 。

现在要支持 $Q$ 次操作：将第 $x$ 行第 $y$ 列的学生移除，然后让第 $x$ 行第 $y$ 行右侧的学生向左移动，接着让第 $m$ 列第 $x$ 行以后的学生向上移动，最后将移除的学生放入第 $n$ 行第 $m$ 列，并输出他的编号。

• $n,m,Q \le 3 \times 10^5$ ，
• 对于一部分数据，保证 $x=1$ 。
• 以下认为 $n,m$ 同阶

$x=1$ 怎么做

这也就意味着只有第 $1$ 行和第 $m$ 列的数据有用，可以使用平衡树进行维护，每次将第 $y$ 个学生取出后放入末尾即可。

不保证 $x=1$ 怎么做

此时如果空间足够，可以仿照 $x=1$ 的做法，对每一行前 $m-1$ 个位置开一个平衡树，第 $i$ 行的平衡树编号为 $i$ 。再对最后一列单独开一个平衡树，编号为 $0$ 。每次提出第 $x$ 个平衡树的第 $y$ 项和第 $0$ 个平衡树的第 $x$ 项，然后交叉拼接即可。

这样做单次操作时间复杂度为 $O(\log n)$ ，但是空间复杂度却达到了 $O(n^2)$ ，这是不可接受的。

对初始的平衡树 $1$ 至 $n$ 进行观察，不难发现如果将第 $i$ 个平衡树里的所有点权值都减去 $(i-1)m$ ，那么 $n$ 棵平衡树将会一模一样！如果一开始将 $rt_1,rt_2,\dots rt_n$ 全都指向这个平衡树，那么初始空间将会只有 $O(n)$ ！接下来的操作为了保证 $n$ 个平衡树互相独立，只需要使用可持久化平衡树进行移动就可以了！

特别的，第 $0$ 个平衡树里存储的为原始编号，所以在交叉拼接时要对权值进行变动。

特别的，权值要开 long long。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=40000100,M=300010;
long long val[N];
int son[N][2],idx,dat[N],n,m,Q,sz[N],rt[M];
void up(int p){sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;}
void copy(int x,int y){
    val[x]=val[y];
    dat[x]=dat[y];
    son[x][0]=son[y][0];
    son[x][1]=son[y][1];
    sz[x]=sz[y];
}
int newnode(int p){
    ++idx;copy(idx,p);
    return idx;
}
int new_node(long long x){
    ++idx;val[idx]=x;dat[idx]=rand();sz[idx]=1;
    return idx;
}
void split(int p,int x,int &l,int &r,int t){
    if(!p){l=r=0;return ;}
    if(t)p=newnode(p);
    if(sz[son[p][0]]<x){
        l=p;
        split(son[p][1],x-sz[son[p][0]]-1,son[p][1],r,t);
    }
    else{
        r=p;
        split(son[p][0],x,l,son[p][0],t);
    }
    up(p);
}
int merge(int l,int r,int t){
    if(!l||!r)return l+r;
    if(dat[l]>dat[r]){
        if(t)l=newnode(l);
        son[l][1]=merge(son[l][1],r,t);
        up(l);
        return l;
    }
    else{
        if(t)r=newnode(r);
        son[r][0]=merge(l,son[r][0],t);
        up(r);
        return r;
    }
}
int main(){
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)rt[0]=merge(rt[0],new_node(1ll*i*m),0);
    for(int i=1;i<m;i++)rt[1]=merge(rt[1],new_node(i),0);
    for(int i=2;i<=n;i++)rt[i]=rt[1];
    while(Q--){
        int x,y;
        cin>>x>>y;
        if(y==m){
            int l,p,r;
            split(rt[0],x,l,r,0);
            split(l,x-1,l,p,0);
            cout<<val[p]<<"\n";
            rt[0]=merge(merge(l,r,0),p,0);
        }
        else{
            int l,p,r;
            split(rt[x],y,l,r,1);
            split(l,y-1,l,p,1);
            cout<<val[p]+1ll*(x-1)*m<<"\n";
            int L,P,R;
            split(rt[0],x,L,R,0);
            split(L,x-1,L,P,0);
            val[P]-=1ll*(x-1)*m;
            val[p]+=1ll*(x-1)*m;
            rt[x]=merge(merge(l,r,1),P,1);
            rt[0]=merge(merge(L,R,0),p,0);
        }
    }
    return 0;
}