平衡树板子求调
  • 板块灌水区
  • 楼主Eterna
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/6 09:01
  • 上次更新2024/10/6 10:17:37
查看原帖
平衡树板子求调
1348260
Eterna楼主2024/10/6 09:01

样例不过。。

#include<bits/stdc++.h>
#define int long long
#define IT set<node>::iterator
#define gc getchar()
#define rd read()
#define N 100005
using namespace std;
inline int read()
{
	int x=0,ss=1,s=gc;
	while(!isdigit(s)&&s!='-')s=gc;
	if(s=='-')ss*=-1,s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc;
	return ss*x;
}
struct treap
{
	int ls,rs,rnd,val,size;
}t[N];
int cnt=0,root=0;
void pushup(int id)
{
	t[id].size=t[t[id].ls].size+t[t[id].rs].size+1;
}
void New(int &k,int x)
{
	++cnt;
	t[cnt]={0,0,rand(),x,1};
	k=cnt;
}
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].rnd<t[y].rnd)
	{
		t[x].rs=merge(t[x].rs,y),pushup(x);
		return x;
	}
	t[y].ls=merge(x,t[y].ls),pushup(y);
	return y;
}
void split(int id,int k,int &x,int &y)
{
	if(!id)
	{
		x=y=0;
		return;
	}
	if(t[id].val<=k)x=id,split(t[x].rs,k,t[x].rs,y),pushup(x);
	else y=id,split(t[y].ls,k,x,t[y].ls),pushup(y);
}
void cl(int &root,int v)
{
	int x=0,y=0,z=0;
	split(root,v,x,z);
	split(x,v-1,x,y);
	y=merge(t[y].ls,t[y].rs);
	root=merge(merge(x,y),z);
}
void insert(int &root,int v)
{
	int x=0,y=0,z=0;
	split(root,v,x,y);
	New(z,v);
	root=merge(merge(x,y),z);
}
int asknum(int id,int rank)
{
	if(rank==t[t[id].ls].size+1)return t[id].val;
	if(rank<=t[t[id].ls].size)return asknum(t[id].ls,rank);
	return asknum(t[id].rs,rank-t[t[id].ls].size-1);
} 
int askrank(int &root,int v)
{
	int x,y;
	split(root,v-1,x,y);
	int rank=t[x].size+1;
	root=merge(x,y);
	return rank;
}
int maxx(int &root,int v)
{
	int x,y,ans;
	split(root,v-1,x,y);
	if(!x)return INT_MIN;
	ans=asknum(x,t[x].size),root=merge(x,y);
	return ans;
}
int minn(int &root,int v)
{
	int x,y,ans;
	split(root,v,x,y);
	if(!y)return INT_MAX;
	ans=asknum(y,1),root=merge(x,y);
	return ans;
}
int n;
signed main()
{
	n=rd;
	while(n--)
	{
		int op=rd,x=rd;
		if(op==1)insert(root,x);
		if(op==2)cl(root,x);
		if(op==3)cout<<askrank(root,x)<<'\n';
		if(op==4)cout<<asknum(root,x)<<'\n';
		if(op==5)cout<<maxx(root,x)<<'\n';
		if(op==6)cout<<minn(root,x)<<'\n';
	}
	return 0;
}
2024/10/6 09:01
加载中...