题解 P3960 【列队】

奇米 · 2020-04-28 09:29:50 · 题解

\mathrm{NOIP2017} 列队

\huge\color{blue}\boxed{\color{Violet}\mathfrak{There\ is \ my \ blog}}

题目意思

• 题目传送门

\mathrm{Sol}

• 前置知识：动态开点线段树

• 首先我们考虑每一次取(x,y)会发生哪些变化：就是最后一列，一行以及x行第m列向前移动了一格。

• 于是我们用n+1棵线段树去维护每一次改变。第1-n棵线段树维护每一行[1,m)的信息。最后一颗维护最后一列的信息。

• 我们以及搞n+1个vector来记录每一棵线段树的信息

• 对于每次操作可以这样子想（分两种情况讨论）

  • y=m

    这个时候取得是最后一列。我们只要看这个元素是不是原来就在最后一列还是从那一次变换得到的，对于这个我们只要搞个vector记录每一次加进去的元素。假设我们找到的这个元素的位置为P如果大于n我们就去vector里找\mathrm{G[n+1][pos-n-1]}的元素(下标为0 )

  • y∈[1,m)

    这是我们只要把(x,y)元素加到n+1棵线段树，以及把x行最后一列即(x,m)从n+1棵线段树移到第x就可以了。其余操作与上面那种情况类似。

• 这样子空间会出大问题。所以一个很套路的想法就是开个动态开点线段树来节约内存。是的时间空间复杂度大概\mathrm{O(n\log n)}

\mathrm{Code}

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=1e7+5;

int n,m,Q,inf,tot,T[N];
vector<int> G[N];

struct Seg
{
    int siz[N],ls[N],rs[N];
    inline int ask(int l,int r,int rt,int x)
    {
        if(l==r) return l;
        int mid=(l+r)/2;
        int now=mid-l+1-siz[ls[rt]];
        if(x<=now) return ask(l,mid,ls[rt],x);
        else return ask(mid+1,r,rs[rt],x-now);
    }
    inline void del(int l,int r,int &rt,int x)
    {
        if(!rt) rt=++tot;
        siz[rt]++;
        if(l==r) return;
        int mid=(l+r)/2;
        if(x<=mid) del(l,mid,ls[rt],x);
        else del(mid+1,r,rs[rt],x);
    }   
    inline int del_lie(int x)
    {
        int pos=ask(1,inf,T[n+1],x);
        del(1,inf,T[n+1],pos);
        return (pos<=n)?(pos-1)*m+m:G[n+1][pos-n-1];
    }
    inline int del_hang(int x,int y)
    {
        int pos=ask(1,inf,T[x],y);
        del(1,inf,T[x],pos);
        return (pos<m)?(x-1)*m+pos:G[x][pos-m];
    }
};
Seg S;

signed main()
{
    n=read();
    m=read();
    Q=read();
    inf=max(n,m)+Q;
    for (;Q--;)
    {
        int x,y;
        x=read();
        y=read();
        if(y==m)
        {
            int P=S.del_lie(x);
            printf("%lld\n",P);
            G[n+1].pb(P);
        }
        else 
        {
            int P=S.del_hang(x,y);
            printf("%lld\n",P);
            G[n+1].pb(P);
            P=S.del_lie(x);
            G[x].pb(P);
        }
    }
    return 0;
}