1,2,11,12AC,其他的玄学MLE
查看原帖
1,2,11,12AC,其他的玄学MLE
177604
LXH5514楼主2021/2/2 10:12

实在不理解,我数组开的挺小的呀,为什么会MLE,如果是TLE我也就认了。

#include<iostream>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
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)+f*(c-'0'),c=getchar();
	return x;
}
const int MAXN=1e5+10;
int n;
int root,a,b,c;
int cnt;
struct node
{
	int l,r;
	int val,key;
	int size;
}shu[MAXN];
void update(int x)
{
	shu[x].size=shu[shu[x].l].size+shu[shu[x].r].size+1;
}
int newnode(int x)
{
	++cnt;
	shu[cnt].key=rand();
	shu[cnt].val=x;
	shu[cnt].size=1;
	return cnt;
}
void split(int now,int val,int &x,int &y)
{
	if(now==0)
	{
		x=y=0;
		return ;
	}
	if(shu[now].val<=val)
	{
		x=now;
		split(shu[now].r,val,shu[now].r,y);
	}else
	{
		y=now;
		split(shu[now].l,val,x,shu[now].l);
	}
	update(now);
}
int merge(int x,int y)
{
	if(x==0||y==0)return x+y;
	if(shu[x].key<shu[y].key)
	{
		shu[x].r=merge(shu[x].r,y);
		update(x);
		return x;
	}
	else 
	{
		shu[y].l=merge(x,shu[y].l);
		update(y);
		return y;
	}
}
void insert(int x)
{
	split(root,x,a,b);
	root=merge(merge(a,newnode(x)),b);
}
void del(int x)
{
	split(root,x-1,a,b);
	split(root,x,b,c);
	b=merge(shu[b].l,shu[b].r);
	root=merge(a,merge(b,c));
}
int getrank1(int x)
{
	split(root,x-1,a,b);
	int ans;
	ans=shu[a].size+1;
	root=merge(a,b);
	return ans;
}
int getrank2(int now,int x)
{
	if(shu[shu[now].l].size==x-1)return shu[now].val;
	if(shu[shu[now].l].size>x-1)return getrank2(shu[now].l,x);
	return getrank2(shu[now].r,x-shu[shu[now].l].size-1);
}
int getnum1(int x)
{
	split(root,x-1,a,b);
	int p=a;
	while(shu[p].r)p=shu[p].r;
	root=merge(a,b);
	return shu[p].val;
}
int getnum2(int x)
{
	split(root,x,a,b);
	int p=b;
	while(shu[p].l)p=shu[p].l;
	root=merge(a,b);
	return shu[p].val;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int opt,x;
		opt=read();
		x=read();
		if(opt==1)insert(x);
		else if(opt==2)del(x);
		else if(opt==3)printf("%d\n",getrank1(x));
		else if(opt==4)printf("%d\n",getrank2(root,x));
		else if(opt==5)printf("%d\n",getnum1(x));
		else if(opt==6)printf("%d\n",getnum2(x));
	}
 	return 0;
}

2021/2/2 10:12
加载中...