N - 土豆的序列

题目大意

让你写一棵平衡树。

题解

写一棵splay。

• 注意：对于询问的数x，如果不在splay里，就先要找到一个在splay里的数替换它，再进行查询操作。

时间复杂度

利用势能分析！

设势函数 R x = log ⁡ ( s i z e x ) R_x=\log (size_x) Rx​=log(sizex​)，可知splay操作的均摊时间复杂度都小于 3 × ( R x ′ − R x ) 3\times(R_x'-R_x) 3×(Rx′​−Rx​)，

因此， n n n个点，进行 m m m次splay的均摊时间复杂度为 O ( n × log ⁡ n + m × log ⁡ n ) O(n\times \log n + m \times \log n) O(n×logn+m×logn)

Tag

splay

code

//pragma GCC optimize (2)
//#pragma G++ optimize (2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define G getchar
#define ls(x) tr[x].son[0]
#define rs(x) tr[x].son[1]
#define fa(x) tr[x].fa
#define si(x) tr[x].si
#define s(x) tr[x].s 
#define v(x) tr[x].v
using namespace std;

int read()
{
    char ch;
    for(ch = G();(ch < '0' || ch > '9') && ch != '-';ch = G());
    int n = 0 , w;
    if (ch == '-')
    {
        w = -1;
        ch = G();
    } else w = 1;
    for(;'0' <= ch && ch <= '9';ch = G())n = (n<<1)+(n<<3)+ch-48;
    return n * w;
}

void write (int x)
{
    if (x > 9)
    {
        write(x / 10);
        putchar(x % 10 + 48);
    }
    else putchar(x + 48);
}

const int N = 3000005;

struct node
{
    int son[2] , fa , v , si , s;
}tr[N * 4];

int n , m , root;
int tot , opv , ops;
int op , x;

int iso (int x) {return (ls(fa(x)) == x)? 0 : 1 ;}

void updata (int x)
{
    si(x) = si(ls(x)) + si(rs(x)) + s(x);
}

void connect (int fa , int x , int pos)
{
    fa(x) = fa;
    tr[fa].son[pos] = x;
}

void rotate (int x)
{
    int fa = fa(x);
    int pos = iso(x) , pf = iso(fa);
    connect(fa(fa) , x , pf);
    connect(fa , tr[x].son[pos ^ 1] , pos);
    connect(x , fa , pos ^ 1);
    updata(fa);
    updata(x);
}

void splay (int x , int to)
{
    int fa;
    to = fa(to);
    for (fa = fa(x) ;fa ^ to;fa = fa(x))
    {
        if (fa(fa) == to)
        {
            rotate(x);
        }
        else
        if (iso(x) ^ iso(fa))//不在同一条线上
        {
             rotate(x);
             rotate(x);
        }
        else
        {
            rotate(fa);
            rotate(x);
        }
    }
    root = rs(0);
}

int find (int x)
{
    if (x == 0) return 0;
    if (v(x) == opv) return x;
    if (v(x) > opv) return find(ls(x)); else return find(rs(x));
}

void find_upper (int x)
{
    if (x == 0) return;
    if (v(x) > opv) ops = min(ops , v(x)) , find_upper(ls(x));
        else find_upper(rs(x));
}

void dx (int x)
{
    v(x) = si(x) = ls(x) = rs(x) = fa(x) = s(x) = 0;
}

void del ()
{
    int x = find(root);
    if (x == 0)return;
    splay(x , root);
    if (s(x) > 1)
    {
        s(x)--;
        si(x)--;
        return;
    }
    if (ls(x) == 0)
    {
        root = rs(0) = rs(x);
        connect(0 , rs(x) , 1);
        dx(x);
        return;
    }
    if (rs(x) == 0)
    {
        root = rs(0) = ls(x);
        connect(0 , ls(x) , 1);
        dx(x);
        return;
    }
    opv = v(x);
    ops = 2147483647;
    find_upper(root);
    opv = ops;
    int pos = find(root);
    splay(pos , rs(x));
    connect(pos , ls(x) , 0);
    connect(0 , pos , 1);
    root = rs(0);
    updata(pos);
    dx(x);
}

void newone ()
{
    tot++;
    s(tot) = si(tot) =1;
    v(tot) = opv;
}

void ins (int x)
{
    if (root == 0)
    {
        newone();
        rs(0) = root = tot;
        return;
    }
    si(x)++;
    if (v(x) == opv)
    {
        s(x)++;
        splay(x , root);
        return;
    }
    if (v(x) > opv)
    {
        if (ls(x) == 0)
        {
            newone();
            connect(x , tot , 0);
            splay(x , root);
            return;
        }
        ins(ls(x));
    }
    else
    {
        if (rs(x) == 0)
        {
            newone();
            connect(x , tot , 1);
            splay(x , root);
            return;
        }
        ins(rs(x));
    }
}

int rak (int v)
{
    opv = v;
    int pos = find(root);
    splay(pos , root);
    return si(ls(pos)) + 1;
}

int kth (int x , int lf)
{
    if (si(ls(x)) < lf && lf <= si(x) - si(rs(x))) return v(x);
    if (si(ls(x)) + s(x) < lf) return kth(rs(x) , lf - si(ls(x)) - s(x));
        else return kth(ls(x) , lf);
}

void find_lower(int x)
{
    if (x == 0) return;
    if (v(x) < opv) ops = max(ops , v(x)) , find_lower(rs(x));
        else find_lower(ls(x));
}

int main()
{
    freopen("n.in" , "r" , stdin);
    //freopen("n.out" , "w" , stdout);
    n = read();
    for (int i = 0; i < n; ++i)
    {
        op = read();
        opv = read();
        switch (op)
        {
            case 1:{
                ins(root);
                break;
            }

            case 2:{
                del();
                break;
            }

            case 3:{
                int pos = find(root);
                if (pos == 0)
                {
                    ops = 2147483647;
                    find_upper(root);
                    opv = ops;
                    // if (ops == -2147483647)printf("0\n");
                    // 	else printf("%d\n", rak(opv));
                }
                if (ops == 2147483647) printf("%d\n", si(root));
                    else printf("%d\n", rak(opv) - 1);
                break;
            }

            case 4:{
                printf("%d\n", kth(root , opv));
                break;
            }

            case 5:{
                ops = 2147483647;
                find_upper(root);
                printf("%d\n", ops);
                break;
            }

            // case 5:{
            //     ops = -2147483647;
            //     find_lower(root);
            //     printf("%d\n", ops);
            //     break;
            // }
        }
    }
    return 0; 
}