求调gpt写的代码
查看原帖
求调gpt写的代码
303531
ReverBer楼主2023/7/6 10:55

以下代码为gpt4所写,只能获得20pts,求调

#include<bits/stdc++.h>
using namespace std;
struct node {
    int l,r;
    int val,key;
    int size;
}fhq[1000000];
int cnt,root;
int New(int val) {
    fhq[++cnt].val=val;
    fhq[cnt].key=rand();
    fhq[cnt].size=1;
    fhq[cnt].l=fhq[cnt].r=0;
    return cnt;
}
void update(int now) {
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void build() {
    New(-2147483647);
    New(2147483647);
    root=1;
    fhq[1].r=2;
    update(1);
}
int getrank(int val) {
    int ans=0,now=root;
    while(now) {
        if(val<=fhq[now].val) now=fhq[now].l;
        else {
            ans+=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    return ans+1;
}
int getnum(int rank) {
    int now=root;
    while(now) {
        if(fhq[fhq[now].l].size+1==rank) break;
        else if(fhq[fhq[now].l].size>=rank) now=fhq[now].l;
        else {
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    return fhq[now].val;
}
int pre(int val) {
    int ans=1,now=root;
    while(now) {
        if(fhq[now].val<val) {
            ans=now;
            now=fhq[now].r;
        }
        else now=fhq[now].l;
    }
    return fhq[ans].val;
}
int next(int val) {
    int ans=2,now=root;
    while(now) {
        if(fhq[now].val>val) {
            ans=now;
            now=fhq[now].l;
        }
        else now=fhq[now].r;
    }
    return fhq[ans].val;
}
void split(int now,int val,int &x,int &y) {
    if(!now) {
        x=y=0;
        return;
    }
    if(fhq[now].val<=val) {
        x=now;
        split(fhq[now].r,val,fhq[now].r,y);
    }
    else {
        y=now;
        split(fhq[now].l,val,x,fhq[now].l);
    }
    update(now);
}
void merge(int &now,int x,int y) {
    if(!x||!y) {
        now=x+y;
        return;
    }
    if(fhq[x].key>fhq[y].key) {
        now=x;
        merge(fhq[now].r,fhq[x].r,y);
    }
    else {
        now=y;
        merge(fhq[now].l,x,fhq[y].l);
    }
    update(now);
}
void insert(int val) {
    int x,y,z;
    split(root,val,x,y);
    z=New(val);
    merge(x,x,z);
    merge(root,x,y);
}
void del(int val) {
    int x,y,z;
    split(root,val-1,x,y);
    split(y,val,y,z);
    merge(y,fhq[y].l,fhq[y].r);
    merge(root,x,y);
}
int main() {
    int n;
    cin>>n;
    build();
    for(int i=1;i<=n;i++) {
        int opt,x;
        cin>>opt>>x;
        if(opt==1) insert(x);
        if(opt==2) del(x);
        if(opt==3) cout<<getrank(x)-1<<endl;
        if(opt==4) cout<<getnum(x+1)<<endl;
        if(opt==5) cout<<pre(x)<<endl;
        if(opt==6) cout<<next(x)<<endl;
    }
    return 0;
}
2023/7/6 10:55
加载中...