86pds求调
查看原帖
86pds求调
995117
pineappler楼主2023/11/5 17:37

就离谱,后面的都过了,错的竟然是前面两个点

#include <bits/stdc++.h>
using namespace std;
const long long N=100005,INF=100000000;
struct node
{
	long long l,r;
	long long key,val;
	long long cnt,siz;
}tr[N*4];
long long root,idx;
long long getnode(long long key)
{
	tr[++idx].key=key;
	tr[idx].val=rand();
	tr[idx].cnt=1;
	tr[idx].siz=1;
	return idx;
}
void pushup(long long u)
{
	tr[u].siz=tr[tr[u].l].siz+tr[u].cnt+tr[tr[u].r].siz;
}
void build()
{
	getnode(-INF);
	getnode(INF);
	root=1;
	tr[1].r=2;
	pushup(root);
}
void zig(long long &u) 
{
	long long v=tr[u].l;
	tr[u].l=tr[v].r;
	tr[v].r=u;
	u=v;
	pushup(tr[u].r);
	pushup(u);
}
void zag(long long &u)
{
	long long v=tr[u].r;
	tr[u].r=tr[v].l;
	tr[v].l=u;
	u=v;
	pushup(tr[u].l);
	pushup(u);
}
void insert(long long &u,long long key)
{
	if(!u) u=getnode(key);
	else if(tr[u].key==key) tr[u].cnt++;
	else if(tr[u].key > key)
	{
		insert(tr[u].l,key);
		if(tr[tr[u].l].val>tr[u].val) zig(u);
	}
	else
	{
		insert(tr[u].r,key);
		if(tr[tr[u].r].val > tr[u].val) zag(u);
	}
	pushup(u);
}
void remove(long long &u,long long key)
{
	if(!u) return;
	if(tr[u].key == key)
	{
		if(tr[u].cnt > 1) tr[u].cnt--;
		else if(tr[u].l || tr[u].r)
		{
			if(!tr[u].r || tr[tr[u].l].val > tr[tr[u].r].val)
			{
				zig(u);
				remove(tr[u].r,key);
			}
			else
			{
				zag(u);
				remove(tr[u].l,key);
			}
		}
		else u=0;
	}
	else
	{
		if(tr[u].key>key) remove(tr[u].l,key);
		else remove(tr[u].r,key);
	}
	pushup(u);
}

long long getrank(long long u,long long key)
{
	if(!u) return 0;
	if(tr[u].key == key) return tr[tr[u].l].siz+1;
	if(tr[u].key > key) return getrank(tr[u].l,key);
	return tr[tr[u].l].siz + tr[u].cnt + getrank(tr[u].r,key);
}

long long getkey(long long u,long long rank)
{
	if(!u) return INF;
	if(tr[tr[u].l].siz >= rank) return getkey(tr[u].l,rank);
	if(tr[tr[u].l].siz + tr[u].cnt >= rank) return tr[u].key;
	return getkey(tr[u].r,rank-tr[tr[u].l].siz-tr[u].cnt);
}
long long getprev(long long u,long long key)
{
	if(!u) return -INF;
	if(tr[u].key >= key) return getprev(tr[u].l,key);
	return max(tr[u].key,getprev(tr[u].r,key));
}
long long getnxt(long long u,long long key)
{
	if(!u) return INF;
	if(tr[u].key <= key) return getnxt(tr[u].r,key);
	return min(tr[u].key,getnxt(tr[u].l,key));
}
int main()
{
	build();
	long long n;
	scanf("%lld",&n);
	while(n--)
	{
		long long opt,x;
		scanf("%lld%lld",&opt,&x);
		if(opt==1) insert(root,x);
		else if(opt==2) remove(root,x);
		else if(opt==3) printf("%lld\n",getrank(root,x)-1);
		else if(opt==4) printf("%lld\n",getkey(root,x+1));
		else if(opt==5) printf("%lld\n",getprev(root,x));
		else printf("%lld\n",getnxt(root,x));
	}
	return 0;
}
2023/11/5 17:37
加载中...