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

前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。

Sylvia 所在的方阵中有 n×m 名学生,方阵的行数为 n,列数为 m。

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

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

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

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

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

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

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

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

链接🔗
[NOIP 2017]列队

题解

因为每次操作,只会产生两种操作,第一种是某行往左移动,让最后一列往前移动

所以我们可以把每一行看成一个序列,一共 n 个序列记为 rt[1-n] ,把最后一列单独拿出来看成一个序列,记为 rt[n+1]

每次操作(x,y),当y不等于m时,选取rt[x]中第y个数删除,并把rt[n+1]中第 x个数加入到rt[x]的末尾,然后把该数删除

中间可以用动态开点线段树维护

编号值可能超过int

代码

#include <cstdio>
#include <algorithm>
#define mid ((l+r)>>1)
#define ll long long
using namespace std;
const ll maxd = 3e5+10;
struct{ll ls,rs,v,sz;}t[maxd*40];
ll rt[maxd],n,m,k,mx,size[maxd],tot,x,y;
void insert(ll &rt,ll l,ll r,ll p,ll num)
{
    if(!rt) rt = ++tot;
    if(l==r) {t[rt].v = num;return ;}
    if(size[p] <= mid)  insert(t[rt].ls,l,mid,p,num);
    else insert(t[rt].rs,mid+1,r,p,num);
}
ll query(ll &rt,ll l,ll r,ll p,ll res,ll flag)
{
    if(!rt) rt = ++tot; t[rt].sz--;
    if(l==r)
    {
        if(t[rt].v) return t[rt].v;
        else if(flag) return t[rt].v = l*m;
        else return t[rt].v = m*(x-1)+l;
    }
    ll cut = t[t[rt].ls].sz + mid-l+1;
    if(res+cut >= p) return query(t[rt].ls,l,mid,p,res,flag);
    else return query(t[rt].rs,mid+1,r,p,res+cut,flag);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    scanf("%lld %lld %lld",&n,&m,&k); mx = max(n,m)+k;    
    for(ll i=1;i<=n;i++) size[i] = m-1; size[n+1] = n; //每个队列的节点数
    for(ll i=1;i<=k;i++)   
    {
        scanf("%lld %lld",&x,&y);      //第x,y 号学生出队
        if(y==m)
        {
            ll num = query(rt[n+1],1,mx,x,0,1); // 找到最后一列的第x行的数 
            printf("%lld\n",num); size[n+1]++;  // 最后一列数加1
            insert(rt[n+1],1,mx,n+1,num);   
        } 
        else
        {
            ll num = query(rt[x],1,mx,y,0,0);
            printf("%lld\n",num);size[n+1]++;size[x]++;
            insert(rt[n+1],1,mx,n+1,num);
            num = query(rt[n+1],1,mx,x,0,1);
            insert(rt[x],1,mx,x,num);
        }
    }
    return 0;
}