不理解,构造的数据也没出 TLE 呃……
难道是我构造得还是太弱了嘛(
#include<cstdio>
#include<cstring>
#define N 1000010
#define inf 2147483647
using namespace std;
struct Tree {
int num,siz,lef,rig;
};
int T,n,tot,bz,x,ans;
Tree t[N];
int FindRank(int id,int x) {
if (t[id].num==x) return t[t[id].lef].siz;
if (t[id].num<x) {
if (t[id].rig==0) return t[id].siz;
return t[t[id].lef].siz+1+FindRank(t[id].rig,x);
}
if (t[id].lef==0) return 0;
return FindRank(t[id].lef,x);
}
int FindNum(int id,int x) {
if (t[t[id].lef].siz>=x) return FindNum(t[id].lef,x);
if (t[t[id].lef].siz==x-1) return t[id].num;
return FindNum(t[id].rig,x-t[id].lef-1);
}
int FindFront(int id,int x) {
if (t[t[id].rig].num<x) return FindFront(t[id].rig,x);
if (t[id].num<x) return id;
if (t[id].lef!=0) FindFront(t[id].lef,x);
return -inf;
}
int FindBack(int id,int x) {
if (t[t[id].lef].num>x) return FindBack(t[id].lef,x);
if (t[id].num>x) return t[id].num;
if (t[id].rig!=0) return FindBack(t[id].rig,x);
return inf;
}
void Insert(int id,int x) {
if (t[id].num>x) {
if (t[id].lef!=0) Insert(t[id].lef,x);
else {
t[id].lef=tot;
t[tot].num=x;
t[tot].siz=1;
}
} else {
if (t[id].rig!=0) Insert(t[id].rig,x);
else {
t[id].rig=tot;
t[tot].num=x;
t[tot].siz=1;
}
}
t[id].siz=t[t[id].lef].siz+t[t[id].rig].siz+1;
}
int main() {
//freopen("5076.in","r",stdin);
// freopen("5076.out","w",stdout);
scanf("%d",&T);
tot=0;
memset(t,0,sizeof(t));
while (T--) {
scanf("%d %d",&bz,&x);
if (bz==1) {
ans=FindRank(1,x)+1;
printf("%d\n",ans);
} else if (bz==2) {
ans=FindNum(1,x);
printf("%d\n",ans);
} else if (bz==3) {
ans=FindFront(1,x);
printf("%d\n",ans);
} else if (bz==4) {
ans=FindBack(1,x);
printf("%d\n",ans);
} else if (bz==5) {
tot++;
if (tot==1) {
t[tot].num=x;
t[tot].siz=1;
} else Insert(1,x);
}
}
return 0;
}