MnZn刚复习第一遍FHQ-Treap 58pts+吸氧后发出赤红色光
查看原帖
MnZn刚复习第一遍FHQ-Treap 58pts+吸氧后发出赤红色光
262620
hez_EX楼主2023/12/17 23:56

rt,这个,这个,还有这个,求调QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#define ls tr[now].lsn
#define rs tr[now].rsn
using namespace std;
struct node
{
	int dat,cnt,sz,hp,lsn,rsn;
}tr[1000005];
int rut,top,n,tsk,u;
inline void read(int &x)
{
	char c=getchar();x=0;
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
}
int mkn(int k)
{
	tr[++top]=(node){k,1,1,rand(),0,0};
	return top;
}
void upd(int now)
{
	tr[now].sz=tr[now].cnt+tr[ls].sz+tr[rs].sz;
}
void spl(int now,int &x,int &y,int k)
{
	if(!now) return (void)(x=y=0);
	if(tr[now].dat<=k) x=now,spl(rs,rs,y,k);
	else y=now,spl(ls,x,ls,k);upd(now);
}
int mrg(int x,int y)
{
	if(!x||!y) return x|y;
	if(tr[x].hp<tr[y].hp) return tr[x].rsn=mrg(tr[x].rsn,y),upd(x),x;
	else return tr[y].lsn=mrg(x,tr[y].lsn),upd(y),y;
}
void ins(int k)
{
	int lft=0,rit=0,mid=0;
	spl(rut,lft,rit,k);
	spl(lft,lft,mid,k-1);
	if(!mid) mid=mkn(k);
	else tr[mid].cnt++,tr[mid].sz++;
	rut=mrg(mrg(lft,mid),rit);
}
void del(int k)
{
	int lft=0,rit=0,mid=0;
	spl(rut,lft,rit,k);
	spl(lft,lft,mid,k-1);
	if(--tr[mid].cnt) tr[mid].sz--,rut=mrg(mrg(lft,mid),rit);
	else rut=mrg(lft,rit);
}
int rnk(int k)
{
	int lft=0,rit=0,ans=0;
	spl(rut,lft,rit,k-1);
	ans=tr[lft].sz+1;
	rut=mrg(lft,rit);
	return ans;
}
int val(int now,int k)
{
	if(tr[ls].sz+1<=k&&k<=tr[ls].sz+tr[now].cnt) return tr[now].dat;
	if(k<=tr[ls].sz) return val(ls,k);
	else return val(rs,k-tr[ls].sz-tr[now].cnt);
}
int pre(int k)
{
	int lft=0,rit=0,ans=0;
	spl(rut,lft,rit,k-1);
	ans=val(lft,tr[lft].sz);
	rut=mrg(lft,rit);
	return ans;
}
int suf(int k)
{
	int lft=0,rit=0,ans=0;
	spl(rut,lft,rit,k);
	ans=val(rit,1);
	rut=mrg(lft,rit);
	return ans;
}
int main()
{
	srand((long long)new char);
	read(n);
	while(n--)
	{
		read(tsk);read(u);
		if(tsk==1) ins(u);
		else if(tsk==2) del(u);
		else if(tsk==3) printf("%d\n",rnk(u));
		else if(tsk==4) printf("%d\n",val(rut,u));
		else if(tsk==5) printf("%d\n",pre(u));
		else printf("%d\n",suf(u));
	}
}
2023/12/17 23:56
加载中...