NOIP2017列队（phalanx）解题报告

列队作为NOIP2017最后一道题，其实并不难，只是相对于其它题目，有点小小的工业

首先，这道题我用splay维护的，如果你不会splay，又想学一下splay，可以来这里学一学，接下来步入正题

首先这道题和往年一样，特殊数据会给你极大的启发，在考试时，看到x=1,只有一行的数据时，我就想到，可以维护一颗平衡数，每次只查询（x，y）由于x=1，所以只要查询队列中第y大即可，那么你再想一想，对于每一行和最后一列维护都分别维护一颗splay即可

但是这样空间并不允许n*m个点，我们发现，大部分点自始至终都是连续的，所以，对于每一个点，我们可以令它表示一排连续的点，当要查询的点在连续的区间中，我们就把这个点拆开，拆成三段，（原来的点可以保留，修改一下信息，再加一个点即可）

所以我们只需要在普通splay上加一个spilt来分裂点即可

inline ll split(int now,ll k)//要分裂编号为now的点，其中第k个是我们要的数字

    {

        splay(now,root);

        k=k+lef[now]-1;//计算出k的数值

        int temp=newnode(k+1,rig[now]);//申请一个新点，区间为k+1至rig[now]

        rig[now]=k-1;//旧点区间右端点改为为k-1

        if(!ch[now][1])//如果没有右儿子就接上

        {

            ch[now][1]=temp;

            fa[temp]=now;

        }

        else//要么就把原来root的右儿子接到新点右儿子上

        {

            int pos=nex(now);

            ch[pos][0]=temp;fa[temp]=pos;

            splay(temp,root);

        }

        return k;

    }

下面是完整代码，大部分操作和splay一样，就不做解释了

#include<bit/stdc++.h>

using namespace std;

typedef int sign;

typedef long long ll;

#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)

#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)

const int N=3e6+5;

bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}

bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}

template<typename T>T read()

{

    T ans=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();

    return ans*f;

}

void file()

{

    #ifndef ONLINE_JUDGE

        freopen("splay.in","r",stdin);

        freopen("splay.out","w",stdout);

    #endif

}

int fa[N],ch[N][2],sz;

ll lef[N],rig[N],size[N];

struct splay_tree

{

    int root;

    inline void clear(int x){fa[x]=ch[x][0]=ch[x][1]=size[x]=lef[x]=rig[x]=0;}

    inline int get(int x){return x==ch[fa[x]][1];}

    inline void push_up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+rig[x]-lef[x]+1;}

    inline void rotate(int x,int &k)

    {

        int old=fa[x],oldfa=fa[old],o=get(x);

        if(old==k)k=x;

        else ch[oldfa][old==ch[oldfa][1]]=x;

        fa[x]=oldfa;fa[old]=x;fa[ch[x][o^1]]=old;

        ch[old][o]=ch[x][o^1];ch[x][o^1]=old;

        push_up(old);push_up(x);

    }

    inline void splay(int x,int &k)

    {

        while(x^k)

        {

            if(fa[x]^k)rotate(get(x)^get(fa[x])?x:fa[x],k);

            rotate(x,k);

        }

        push_up(x);

    }

    inline int find_last()//因为插到最后面，所以一直往右儿子走

    {

        int now=root;

        while(ch[now][1])now=ch[now][1];

        return now;

    }

    inline int newnode(ll l,ll r)

    {

        ++sz;lef[sz]=l;rig[sz]=r;size[sz]=r-l+1;

        return sz;

    }

    inline void init(ll l,ll r){root=newnode(l,r);}

    inline void insert(ll v)

    {

        int now=newnode(v,v);

        int pos=find_last();

        ch[pos][1]=now;fa[now]=pos;

        splay(now,root);

    }

    inline int pre(int x)

    {

        int now=ch[x][0];

        while(ch[now][1])now=ch[now][1];

        return now;

    }

    inline int nex(int x)

    {

        int now=ch[x][1];

        while(ch[now][0])now=ch[now][0];

        return now;

    }

    inline ll split(int now,ll k)

    {

        splay(now,root);

        k=k+lef[now]-1;

        int temp=newnode(k+1,rig[now]);

        rig[now]=k-1;

        if(!ch[now][1])

        {

            ch[now][1]=temp;

            fa[temp]=now;

        }

        else

        {

            int pos=nex(now);

            ch[pos][0]=temp;fa[temp]=pos;

            splay(temp,root);

        }

        return k;

    }

    inline ll find_ans(ll x)//找第k大

    {

        int now=root;ll len;

        while(1)

        {

            if(x<=size[ch[now][0]])now=ch[now][0];

            else

            {

                x-=size[ch[now][0]];

                len=rig[now]-lef[now]+1;

                if(x<=len)//要找的点在这个点的区间中

                {

	             //ps：如果这个点左区间等于右区间，不必删掉它（很慢），把左端点++，这样这个点的长度就变成0了，不影响这棵树

                     if(x==1)

                     {

                        ll res=lef[now];

                        lef[now]++;

                        splay(now,root);

                        push_up(now);

                        return res;

                     }

                     if(x==len)

                     {

                        ll res=rig[now];

                        rig[now]--;

                        splay(now,root);

                        push_up(now);

                        return res;

                     }

                     else return split(now,x);

                }

                x=x-(rig[now]-lef[now]+1);

                now=ch[now][1];

            }

        }

    }

}s[N];

ll n,m,q;

inline void input(){n=read<ll>();m=read<ll>();q=read<ll>();}

inline void init()

{

    For(i,1,n)s[i].init(m*(i-1)+1,i*m-1);

    s[0].init(m,m);

    For(i,2,n)s[0].insert(i*m);

}

inline void work()

{

    int x,y;

    ll v;

    while(q--)

    {

        x=read<int>(),y=read<int>();

        if(y==m)

        {

            printf("%lld\n",v=s[0].find_ans(x));

            s[0].insert(v);

        }

        else

        {

            printf("%lld\n",v=s[x].find_ans(y));

            s[x].insert(s[0].find_ans(x));

            s[0].insert(v);

        }

    }

}

int main()

{

    file();

    input();

    init();

    work();

    return 0;

}

巴特西

NOIP2017列队（phalanx）解题报告

最新文章

热门文章