50D：Treap的简易模板
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<set>
#include<stack>
#include<map>
#include<bitset>
#include<ctime>
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(s<t[now].s)
{
now=t[now].lc;
continue;
}
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].sum<t[t[x].rc].sum)
zag(t[x].lc);
else
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???"<<endl;
if(s<t[now].s)
{
pre=now;
now=t[now].lc;
continue;
}
if(s>t[now].s)
{
pre=now;
now=t[now].rc;
continue;
}
}
if(s<t[pre].s)
t[pre].lc=w;
if(s>t[pre].s)
t[pre].rc=w;
t[w].fa=pre;
while(t[w].sum<t[t[w].fa].sum)
{
if(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;
}
评论