TLE求调
查看原帖
TLE求调
94659
Kuoy楼主2024/9/15 14:40

不理解,构造的数据也没出 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;
}
2024/9/15 14:40
加载中...