Treap 템플릿(단순)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef int ll;
typedef unsigned long long ull;
inline ll read()
{
    char k=0;char ls;ls=getchar();for(;ls<'0'||ls>'9';k=ls,ls=getchar());
    ll x=0;for(;ls>='0'&&ls<='9';ls=getchar())x=x*10+ls-'0';
    if(k=='-')x=0-x;return x;
}
struct E{
    ll lc,rc;
    ll s,sum;
    ll fa;
}t[1000050];
ll w;
ll size;
ll root;

inline ll find(ll s)//   
{
    ll now=root;
    while(now)
    {
        if(t[now].s==s)
        return now;
        if(scontinue;
        }
        if(s>t[now].s)
        {
            now=t[now].rc;
            continue;
        }
    }
    return 0;
}

ll maxn()//    
{
    ll now=root;
    while(1)
    {
        if(t[now].rc==0)
        return now;
        now=t[now].rc;
    }
}

ll minn()//    
{
    ll now=root;
    while(1)
    {
        if(t[now].lc==0)
        return now;
        now=t[now].lc;
    }
}

void zig(ll x)//   
{
    if(root==t[x].fa)
    root=x;
    ll ff=t[t[x].fa].fa;
    t[t[x].fa].fa=x;
    if(ff!=0)
    {
        if(t[ff].lc==t[x].fa)
        t[ff].lc=x;
        if(t[ff].rc==t[x].fa)
        t[ff].rc=x;
    }
    if(t[x].lc!=0)
    t[t[x].lc].fa=t[x].fa;
    t[t[x].fa].rc=t[x].lc;
    t[x].lc=t[x].fa;
    t[x].fa=ff;
    return;
}

void zag(ll x)//   
{
    if(root==t[x].fa)
    root=x;
    ll ff=t[t[x].fa].fa;
    t[t[x].fa].fa=x;
    if(ff!=0)
    {
        if(t[ff].lc==t[x].fa)
        t[ff].lc=x;
        if(t[ff].rc==t[x].fa)
        t[ff].rc=x;
    }
    if(t[x].rc!=0)
    t[t[x].rc].fa=t[x].fa;
    t[t[x].fa].lc=t[x].rc;
    t[x].rc=t[x].fa;
    t[x].fa=ff;
    return;
}

void strike_off(ll x)//   
{
    while(t[x].lc!=0||t[x].rc!=0)
    {
        if(t[x].lc!=0&&t[x].rc==0)
        {zag(t[x].lc);continue;}

        if(t[x].rc!=0&&t[x].lc==0)
        {zig(t[x].rc);continue;}

        if(t[x].lc!=0&&t[x].rc!=0)
        {
            if(t[t[x].lc].sumelse
            zig(t[x].rc);
        }
    }
    if(t[x].fa!=0)
    {
        if(t[t[x].fa].lc==x)
        t[t[x].fa].lc=0;
        if(t[t[x].fa].rc==x)
        t[t[x].fa].rc=0;
    }
    --size;
    return;
}

void insert(ll s)//   
{
    ++size;
    t[++w].s=s;
    t[w].sum=rand()%1000050;
    if(size==1)
    {
        root=w;
        return;
    }
    ll pre=root;
    ll now=root;
    while(now!=0)
    {
        if(s==t[now].s)
        cout<<"shenmegui???"<if(scontinue;
        }
        if(s>t[now].s)
        {
            pre=now;
            now=t[now].rc;
            continue;
        }
    }
    if(sif(s>t[pre].s)
    t[pre].rc=w;
    t[w].fa=pre;

    while(t[w].sumif(t[t[w].fa].lc==w)
        {
            zag(w);
            continue;
        }
        if(t[t[w].fa].rc==w)
        {
            zig(w);
            continue;
        }
    }
    return;
}

int main()
{
    srand(19981017);
    return 0;
}