NOIP2017D2T3 列队

wjh15101051's space

卧薪尝胆，厚积薄发。

NOIP2017D2T3 列队

Date: Sun Sep 02 10:10:03 CST 2018

In Category: NoCategory

Description：

一个 $n\times m$ 的方阵，每次有一个人离队，然后所有人向左看齐再向前看齐，离队的人补到最后的空位上，每次输出离队的人的编号。

$1\le n,m\le3\times 10^5$

Solution：

用 $splay$ 维护人的变化，那么一次操作就是两次 $addback$ 操作和两次 $remove$ 操作，但是由于数据范围太大所以只能动态开点，注意当当前节点有子树时细节很多。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 300010

int root[MAXN],rootr;

typedef long long ll;

struct node

{

    int c[2],fa,siz;

    ll l,r,v;

}t[MAXN * 30];

int ptr = 0;

inline int newnode(){return ++ptr;}

inline void build(int &rt,ll l,ll r){rt = newnode();t[rt].l = l;t[rt].r = r;t[rt].siz = r - l + 1;return;}

inline int id(int x){return t[t[x].fa].c[0] == x ? 0 : 1;}

inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

inline void maintain(int rt){t[rt].siz = t[t[rt].c[0]].siz + t[t[rt].c[1]].siz + t[rt].r - t[rt].l + 1;return;}

inline void rotate(int x)

{

    register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

    connect(t[x].c[fx ^ 1],y,fx);

    connect(y,x,fx ^ 1);

    connect(x,z,fy);

    maintain(y);maintain(x);

    return;

}

inline void splay(int x,int &k)

{

    register int to = t[k].fa;

    while(t[x].fa != to)

    {

        int y = t[x].fa;

        if(t[y].fa == to){rotate(x);break;}

        if(id(x) == id(y)){rotate(y);rotate(x);}

        else{rotate(x);rotate(x);}

    }

    k = x;

    return;

}

void buildr(int &rt,ll l,ll r,int f)

{

	if(l > r)return;

	rt = newnode();

	register ll mid = (l + r) >> 1;

	t[rt].l = t[rt].r = t[rt].v = mid * (ll)m;

	t[rt].siz = 1;t[rt].fa = f;

	buildr(t[rt].c[0],l,mid - 1,rt);

	buildr(t[rt].c[1],mid + 1,r,rt);

	maintain(rt);

	return;

}

inline void createnode(int &rt,ll l,ll r,int f)

{

	if(l > r)return;

	rt = newnode();

	t[rt].l = l;t[rt].r = r;

	if(l == r)t[rt].v = l;

	t[rt].siz = r - l + 1;t[rt].fa = f;

	return;

}

inline void expand(int rt)

{

	if(t[rt].l == t[rt].r)return;

	register ll mid = ((t[rt].l + t[rt].r) >> 1);

	if(t[rt].c[0] == 0)

	{

		createnode(t[rt].c[0],t[rt].l,mid - 1,rt);

	}

	else

	{

		if(t[rt].l <= mid - 1)

		{

			register int k;createnode(k,t[rt].l,mid - 1,rt);

			t[k].c[0] = t[rt].c[0];t[t[rt].c[0]].fa = k;t[rt].c[0] = k;

			maintain(t[rt].c[0]);

		}

	}

	if(t[rt].c[1] == 0)

	{

		createnode(t[rt].c[1],mid + 1,t[rt].r,rt);

	}

	else

	{

		if(mid + 1 <= t[rt].r)

		{

			register int k;createnode(k,mid + 1,t[rt].r,rt);

			t[k].c[1] = t[rt].c[1];t[t[rt].c[1]].fa = k;t[rt].c[1] = k;

			maintain(t[rt].c[1]);

		}

	}

    t[rt].l = t[rt].r = t[rt].v = mid;

    return;

}

inline int findkth(int &rt,int k)

{

    register int cur = rt;

    while(true)

    {//cout << t[cur].l << " " << t[cur].r << " " << k << " " << t[t[cur].c[0]].siz << endl;

    	if(k <= t[t[cur].c[0]].siz)

    	{

			cur = t[cur].c[0];

			continue;

		}

		if(k > t[t[cur].c[0]].siz + t[cur].r - t[cur].l + 1)

		{

			k -= t[t[cur].c[0]].siz + t[cur].r - t[cur].l + 1;

			cur = t[cur].c[1];

			continue;

		}

        expand(cur);

        if(k <= t[t[cur].c[0]].siz)

        {

            cur = t[cur].c[0];

        }

        else if(k > t[t[cur].c[0]].siz + t[cur].r - t[cur].l + 1)

        {

            k -= t[t[cur].c[0]].siz + t[cur].r - t[cur].l + 1;

            cur = t[cur].c[1];

        }

        else

        {//cout << "return" << endl;

            splay(cur,rt);

            return cur;

        }

    }

}

inline void remove(int &rt,int k)

{

    splay(k,rt);

    if(t[rt].c[0] == 0 && t[rt].c[1] == 0)

    {

        rt = 0;

        return;

    }

    if(t[rt].c[0] == 0)

    {

        rt = t[rt].c[1];t[rt].fa = 0;

        return;

    }

    if(t[rt].c[1] == 0)

    {

        rt = t[rt].c[0];t[rt].fa = 0;

        return;

    }

    register int nrt = t[rt].c[1];

    while(t[nrt].c[0] != 0)nrt = t[nrt].c[0];

    splay(nrt,rt);

    splay(k,t[rt].c[0]);

    t[rt].c[0] = t[k].c[0];t[t[k].c[0]].fa = rt;

    maintain(rt);

    return;

}

inline void addback(int &rt,ll v)

{

	if(rt == 0)

	{

		createnode(rt,v,v,0);

		return;

	}

    register int cur = rt;

    while(t[cur].c[1] != 0)

	{

		++t[cur].siz;

		cur = t[cur].c[1];

	}

	++t[cur].siz;

    createnode(t[cur].c[1],v,v,cur);

    splay(t[cur].c[1],rt);

    return;

}

inline void query(int a,int b)

{

	if(b == m)

	{

		register int k = findkth(rootr,a);

		printf("%lld\n",t[k].v);

		addback(rootr,t[k].v);

		remove(rootr,k);

		return;

	}

    register int k = findkth(root[a],b);

    printf("%lld\n",t[k].l);

    addback(rootr,t[k].l);

    remove(root[a],k);

    register int nk = findkth(rootr,a);

    addback(root[a],t[nk].v);

    remove(rootr,nk);

    return;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

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

	for(register int i = 1;i <= n;++i)build(root[i],(ll)(i - 1) * m + 1,(ll)i * m - 1);

	buildr(rootr,1,(ll)n,0);

	register int a,b;

	for(register int i = 1;i <= q;++i)

	{

		a = read();b = read();

		query(a,b);

	}

	return 0;

}

In tag: 数据结构-splay 数据结构-动态开点

wjh15101051