学哦爱的大哥哥大姐姐们,求求帮帮我
查看原帖
学哦爱的大哥哥大姐姐们,求求帮帮我
247269
MSqwq楼主2023/5/8 19:29

有点麻木了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),c=getchar();}
	return x*f;
}

inline void wr(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)wr(x/10);putchar(x%10+'0');
}

const int N=1e5+10;
struct fhq{
	int ls,rs;
	int val,key,si;
}t[N<<3];
int tot,rt;
int built(int val){t[++tot]={0,0,val,rand(),1};return tot;}
void update(int p){t[p].si=t[t[p].ls].si+t[t[p].rs].si+1;}
void split(int p,int val,int &x,int &y)
{
	if(!p){x=y=0;return;}
	if(t[p].val<=val)x=p,split(t[p].rs,val,t[p].rs,y);	
	else y=p,split(t[p].ls,val,x,t[p].ls);
	update(p);
}
int merge(int x,int y)
{
	if(!x||!y)return x+y;
	if(t[x].key<t[y].key)
	{
		t[x].rs=merge(t[x].rs,y);
		update(x);return x;
	}
	t[y].ls=merge(x,t[y].ls);
	update(y);return y;
}
int kth(int p,int k)
{
	if(k==t[t[p].ls].si+1)return k;
	if(k<=t[t[p].ls].si)return kth(t[p].ls,k);
	return kth(t[p].rs,k-(t[t[p].ls].si+1));
}
void insert(int val)
{
	int x,y;split(rt,val,x,y);
	rt=merge(merge(x,built(val)),y);
}
void del(int val)
{
	int x,y,z;
	split(rt,val,x,z),split(x,val-1,x,y);
	y=merge(t[y].ls,t[y].rs);
	rt=merge(merge(x,y),z);
}
int pre(int val)
{
	int x,y,p;
	split(rt,val-1,x,y);p=x;
	while(t[p].rs)p=t[p].rs;
	rt=merge(x,y);return t[p].val;
}
int nex(int val)
{
	int x,y,p;
	split(rt,val,x,y);p=y;
	while(t[p].ls)p=t[p].ls;
	rt=merge(x,y);return t[p].val;
}
int getrk(int val)
{
	int x,y;split(rt,val-1,x,y);
	rt=merge(x,y);return t[x].si+1;
}
int main()
{
	srand(time(0));
    int n=read();
	for(int i=1;i<=n;i++)
	{
		int op=read(),x=read();
		if(op==1)insert(x);
		if(op==2)del(x);
		if(op==3)wr(getrk(x)),puts("");
		if(op==4)wr(t[kth(rt,x)].val),puts("");
		if(op==5)wr(pre(x)),puts("");
		if(op==6)wr(nex(x)),puts("");
	}
	return 0;
}
2023/5/8 19:29
加载中...