NOIp2017 列队（线段树）

嘛。。两年前的题目了，想起第一次参加提高组还骗了一个省二回来呢。。。跟同学吹了好久的。。。

离退役又近了一骗博客啊。。

闲聊结束。

照常化简：给定一个1-n*m编号的矩阵，每次删除一个位置，然后左边向右补，之后后面向前补，最后空出来的位置再由刚刚删去的点补上，求每次删除的点的编号。

当年也是暴力，奔着30pts就去了，结果奈何手欠数组开大了全部MLE。。。

但是正解也就从这里延伸。

首先，直接地，删除，增加，维护序列，能想到的东西差不多就是平衡树了。。。

但是，考场上大打Splay绝对不可能（日常也不可能打，我是连线段树都能写错的蒟蒻）

所以果断放弃。。

通过观察，晓得每次删除/填补只会有当前行和最后一列，还有最后一行的一个点变化。

于是，经过一年的思考和集训老师的解说，我明白了，可以用线段树写。

把用过的扔到后面，然后通过线段树的操作获得答案（下面再讲）

开n+1个线段树，维护每一行和最后一列。

为了防止数组出锅，我们要尽可能开大，所以要开（max（n，m）+q）*（n+1）个，然鹅这个数组应该达到了TB级别。。。

最终数据有900亿人（超级教官&&银河军训），而询问数量却很小，也就是说，有很多空间都没有用过，所以使用动态开点线段树，需要用的时候再找内存要空间。

然后来考虑怎么查询&&维护。

首先，线段树没有平衡树这么多神仙操作，所以要用公式或者记录某些东西来获得编号

如果没有动过，一切好说，直接乘法加法计算即可
如果是最后一列直接搞

问题就在于怎么查中间的。

记录一下每一行缺了多少人，（1-n之内跑了多少，下统称size），然后每次只需要比较查询的那个大小和size的大小就可以获得“方向”了。

如果size大，说明要求的东西不在原序列里，要另查
如果size小，说明我们可以继续在当前区间乱搞了

怎么乱搞呢？记录一下每一行缺的是哪个点，如果初始没有动的话直接公式搞定如果中间动过的话，就一系列骚操作通过记录的东西获得答案。

然后每次用答案去更新序列

然后就是代码了，有注释

#include<bits/stdc++.h>

#define ll long long

#define ill inline long long

using namespace std;

inline int read()

{

    int x=,f=;char s=getchar();

    while(s>''||s<''){if(s=='-')f=-;s=getchar();}

    while(s<=''&&s>=''){x=x*+s-'';s=getchar();}

    return x*f;

}

const ll maxn=6e6+;

int n,m,q;

int size[maxn];//第i行1-n中有多少缺失的（即动态开多少点）

ll tre[maxn];//每一行却的点的编号 （动态变化，每次只缺一个）

int ls[maxn];

int rs[maxn];

int R[maxn];//行/最后一列的长度（开完之后）

int cnt;

ill find_row(int l,int r,int x,int y,int &k)

{

    if(!k)

    k=++cnt;

    size[k]++;

    if(l==r)

    {

        if(tre[k]==)return (ll)(x-)*m+r;

        else return tre[k];

    }

    int mid=l+r>>;

    if(mid-l+-size[ls[k]]>=y)return find_row(l,mid,x,y,ls[k]);

    else{ y-=mid-l+-size[ls[k]];return find_row(mid+,r,x,y,rs[k]);}

}

ill findline(int l,int r,int x,int y,int &k)

{

    if(!k)

    k=++cnt;

    size[k]++;

    if(l==r)

    {

        if(tre[k]==)return (ll)(l-)*m+y;

        else return tre[k];

    }

    int mid=l+r>>;

    if(mid-l+-size[ls[k]]>=x)return findline(l,mid,x,y,ls[k]);

    else {x-=mid-l+-size[ls[k]];return findline(mid+,r,x,y,rs[k]);}

}

void add(int l,int r,ll v,int x,int &k)

{

    if(!k)

    k=++cnt;

    if(l==r)

    {

        tre[k]=v;

        return;

    }

    int mid=l+r>>;

    if(x<=mid)add(l,mid,v,x,ls[k]);

    else      add(mid+,r,v,x,rs[k]);

}

int main()

{

    //scanf("%d%d%d",&n,&m,&q);

    n=read();

    m=read();

    q=read();

    int r=max(n,m)+q;

    cnt=n+;

    while(q--)

    {

        int x,y;

        x=read();

        y=read();//scanf("%d%d",&x,&y);

        if(y==m)

        {

            int k=n+;

            ll ans=findline(,r,x,y,k);

            printf("%lld\n",ans);

            R[n+]++;add(,r,ans,R[n+]+n,k);

        }

        else

        {

            int k=n+;

            ll ans=find_row(,r,x,y,x);

            ll tem=findline(,r,x,m,k);

            printf("%lld\n",ans);

            R[x]++;add(,r,tem,R[x]+m-,x);

            R[n+]++;add(,r,ans,R[n+]+n,k);

        }

    }

    return ;

}

巴特西

NOIp2017 列队（线段树）

最新文章

热门文章