Treapテンプレート(中級版)
18863 ワード
サポート:挿入削除検索最大値最小値寸法レコード(重複要素をサポート)
#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'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;//
ll size;//
ll js;//
}t[1000050];
ll w;
ll size;
ll root;
inline ll find(ll s)//
{
if(size==0)
return 0;
ll now=root;
while(now)
{
if(t[now].s==s)
return now;
if(s.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 update(ll x)//
{
ll now=root;
while(1)
{
--t[now].size;
if(now==x)return;
if(t[x].s.s)
{
now=t[now].lc;
continue;
}
if(t[x].s>t[now].s)
{
now=t[now].rc;
continue;
}
}
return;
}
void zig(ll x)//
{
t[t[x].fa].size-=t[t[x].rc].size;
t[t[x].fa].size-=t[x].js;
t[x].size+=t[t[t[x].fa].lc].size;
t[x].size+=t[t[x].fa].js;
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)//
{
t[t[x].fa].size-=t[t[x].lc].size;
t[t[x].fa].size-=t[x].js;
t[x].size+=t[t[t[x].fa].rc].size;
t[x].size+=t[t[x].fa].js;
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].sumx].rc].sum)
zag(t[x].lc);
else
zig(t[x].rc);
}
}
update(x);
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;
if(size==0)
root=0;
return;
}
void delete_(ll s)//
{
ll x=find(s);
if(x==0)
return;
if(t[x].js>1)
{
--t[x].js;
--size;
update(x);
return;
}
else
strike_off(x);
return;
}
void insert(ll s)//
{
++size;
t[++w].s=s;
t[w].sum=rand()%1000050;
t[w].size=1;
t[w].js=1;
if(size==1)
{
root=w;
return;
}
ll pre=root;
ll now=root;
while(now!=0)
{
if(s==t[now].s)
{
++t[now].size;
++t[now].js;
--w;
return;
}
if(s.s)
{
++t[now].size;
pre=now;
now=t[now].lc;
continue;
}
if(s>t[now].s)
{
++t[now].size;
pre=now;
now=t[now].rc;
continue;
}
}
if(s.s)
t[pre].lc=w;
if(s>t[pre].s)
t[pre].rc=w;
t[w].fa=pre;
while(t[w].sum.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;
}