实在不理解,我数组开的挺小的呀,为什么会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;
}