全码
优点:码量短
写错了的话，\(TLE,MLE,Wa\)全家桶
包含合并操作
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 1e6+5;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int rand()
{
uniform_int_distribution<ll>rg(LONG_LONG_MIN,LONG_LONG_MAX);
return rg(rnd)%INT_MAX;
}
struct FHQ_Treap
{
int ch[N][2],sz[N],rt,tot,id[N],v[N];
inline void pushup(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}
inline int newnode(int x)
{
sz[++tot]=1;v[tot]=x;id[tot]=rand();
return tot;
}
inline int merge(int x,int y)
{
if(!x||!y)return x^y;
if(id[x]<id[y])return ch[x][1]=merge(ch[x][1],y),pushup(x),x;
return ch[y][0]=merge(x,ch[y][0]),pushup(y),y;
}
inline void split(int now,int k,int &x,int &y)
{
if(!now)x=0,y=0;
else
{
if(k>=v[now])x=now,split(ch[now][1],k,ch[now][1],y);
else y=now,split(ch[now][0],k,x,ch[now][0]);
pushup(now);
}
}
inline void insert(int k)
{
int x,y;
split(rt,k,x,y);
rt=merge(merge(x,newnode(k)),y);
}
inline void del(int k)
{
int x,y,z;
split(rt,k,x,y);
split(x,k-1,x,z);//attention is x not rt
z=merge(ch[z][0],ch[z][1]);rt=merge(merge(x,z),y);
}
inline int kth(int now,int k)
{
while(1)
{
if(k<=sz[ch[now][0]])now=ch[now][0];
else if(k==sz[ch[now][0]]+1)return now;
else k-=sz[ch[now][0]]+1,now=ch[now][1];
}
}
inline int rank(int k)
{
int x,y;
split(rt,k-1,x,y);int ans=sz[x]+1;
return rt=merge(x,y),ans;
}
inline int pre(int k)
{
int x,y,ans;
split(rt,k-1,x,y);
ans=v[kth(x,sz[x])];
return rt=merge(x,y),ans;
}
inline int nxt(int k)
{
int x,y,ans;
split(rt,k,x,y);
ans=v[kth(y,1)];
return rt=merge(x,y),ans;
}
}tree;
int n;
int main()
{
speed();
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
cin>>n;
int opt,x;
for(int i=1;i<=n;i++)
{
cin>>opt>>x;
if(opt==1)
{
tree.insert(x);
}else if(opt==2)
{
tree.del(x);
}else if(opt==3)
{
cout<<tree.rank(x)<<endl;
}else if(opt==4)
{
cout<<tree.v[tree.kth(tree.rt,x)]<<endl;
}else if(opt==5)
{
cout<<tree.pre(x)<<endl;
}else
{
cout<<tree.nxt(x)<<endl;
}
}
return 0;
}
核心函数是合并和分离，所以都是基于\(rand\)维护
合并
格外要注意的是合并\(x\)和\(y\)要保证\(x\)中的所有元素都小于\(y\)中的,这里采用\(id\)小的在上面
int merge(int x,int y)
{
if(!x||!y)return x^y;//返回非0项
if(id[x]<id[y])return ch[x][1]=merge(ch[x][1],y),up(x),x;
return ch[y][0]=merge(x,ch[y][0]),up(y),y;
}
分裂操作，递归分裂,注意细节
注意\(x\)包含\(k\),\(y\)不包含\(k\)
inline void split(int now,int k,int &x,int &y)
{
if(!now)x=0,y=0;
else
{
if(k>=v[now])x=now,split(ch[now][1],k,ch[now][1],y);//一定要记得更新x,y
else y=now,split(ch[now][0],k,x,ch[now][0]);//一定要记得更新x,y
pushup(now);
}
}
插入，删除
inline void insert(int k)
{
int x,y;
split(rt,k,x,y);
rt=merge(merge(x,newnode(k)),y);
}
inline void del(int k)
{
int x,y,z;
split(rt,k,x,y);
split(x,k-1,x,z);//attention is x not rt
z=merge(ch[z][0],ch[z][1]);rt=merge(merge(x,z),y);
}
查询第\(k\)小
inline int kth(int now,int k)
{
while(1)
{
if(k<=sz[ch[now][0]])now=ch[now][0];
else if(k==sz[ch[now][0]]+1)return now;
else k-=sz[ch[now][0]]+1,now=ch[now][1];
}
}
查询权值的排名
inline int rank(int k)
{
int x,y;
split(rt,k-1,x,y);int ans=sz[x]+1;
return rt=merge(x,y),ans;
}
查询前驱，后继
inline int pre(int k)
{
int x,y,ans;
split(rt,k-1,x,y);
ans=v[kth(x,sz[x])];
return rt=merge(x,y),ans;
}
inline int nxt(int k)
{
int x,y,ans;
split(rt,k,x,y);
ans=v[kth(y,1)];
return rt=merge(x,y),ans;
}