[HDU4585]Shaolin

Problem

问你一个数的前驱和后继

Solution

Treap模板题

Notice

注意输出那个人的编号

Code

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; i++)

#define per(i, a, b) for (reg i = a; i >= b; i--)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

const int INF = 1e9, N = 100001;

const double eps = 1e-6, phi = acos(-1.0);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

int point = 0, pre, suf, root;

struct node

{

    int Val[N + 5], Level[N + 5], Size[N + 5], Son[2][N + 5], Label[N + 5];

    inline void up(int u)

    {

        Size[u] = Size[Son[0][u]] + Size[Son[1][u]] + 1;

    }

    inline void Newnode(int &u, int v, int t)

    {

        u = ++point;

        Level[u] = rand(), Val[u] = v, Label[u] = t;

        Size[u] = 1, Son[0][u] = Son[1][u] = 0;

    }

    inline void Lturn(int &x)

    {

        int y = Son[1][x]; Son[1][x] = Son[0][y], Son[0][y] = x;

        Size[y] = Size[x]; up(x); x = y;

    }

    inline void Rturn(int &x)

    {

        int y = Son[0][x]; Son[0][x] = Son[1][y], Son[1][y] = x;

        Size[y] = Size[x]; up(x); x = y;

    }

    void Insert(int &u, int t, int tt)

    {

        if (u == 0)

        {

            Newnode(u, t, tt);

            return;

        }

        Size[u]++;

        if (t < Val[u])

        {

            Insert(Son[0][u], t, tt);

            if (Level[Son[0][u]] < Level[u]) Rturn(u);

        }

        else if (t > Val[u])

        {

            Insert(Son[1][u], t, tt);

            if (Level[Son[1][u]] < Level[u]) Lturn(u);

        }

    }

    int Find_num(int u, int t)

    {

        if (!u) return 0;

        if (t <= Size[Son[0][u]]) return Find_num(Son[0][u], t);

        else if (t <= Size[Son[0][u]] + 1) return u;

        else return Find_num(Son[1][u], t - Size[Son[0][u]] - 1);

    }

    void Find_pre(int u, int t)

    {

        if (!u) return;

        if (t > Val[u])

        {

            pre = u;

            Find_pre(Son[1][u], t);

        }

        else Find_pre(Son[0][u], t);

    }

    void Find_suf(int u, int t)

    {

        if (!u) return;

        if (t < Val[u])

        {

            suf = u;

            Find_suf(Son[0][u], t);

        }

        else Find_suf(Son[1][u], t);

    }

}Treap;

int sqz()

{

    int n;

    while (~scanf("%d", &n) && n)

    {

        root = point = 0;

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

        printf("%d 1\n", x);

        Treap.Insert(root, y, x);

        rep(i, 2, n)

        {

            pre = suf = -1;

            x = read(), y = read();

            Treap.Find_pre(root, y);

            Treap.Find_suf(root, y);

            Treap.Insert(root, y, x);

            printf("%d ", x);

            if (pre == -1) printf("%d\n", Treap.Label[suf]);

            else if (suf == -1) printf("%d\n", Treap.Label[pre]);

            else if (y - Treap.Val[pre] <= Treap.Val[suf] - y) printf("%d\n", Treap.Label[pre]);

            else printf("%d\n", Treap.Label[suf]);

        }

    }

}