4pts求调
查看原帖
4pts求调
1164692
lijianACE楼主2025/1/5 11:50

只对了#2,其余全WA。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int root[N],cnt=0,n,op,x,v,vers;;
struct Node{
    int ls,rs,key,pri,size;
};
Node tree[N<<7];
void update(int p){
    tree[p].size=tree[tree[p].ls].size+tree[tree[p].rs].size+1;
}
void newnode(int x){
    tree[++cnt].size=1;
    tree[cnt].ls=0;
    tree[cnt].rs=0;
    tree[cnt].key=x;
    tree[cnt].pri=rand();
}
int findk(int p,int k){
    if(k==tree[tree[p].ls].size+1) return p;
    if(k<=tree[tree[p].ls].size) return findk(tree[p].ls,k);
    else return findk(tree[p].rs,k-tree[tree[p].ls].size-1);
}
void split(int p,int x,int &L,int &R){
    if(p==0){
        L=0;
        R=0;
        return;
    }
    if(tree[p].key<=x){
        L=p;
        split(tree[p].rs,x,tree[p].rs,R);
    }
    else{
        R=p;
        split(tree[p].ls,x,L,tree[p].ls);
    }
    update(p);
}
int Merge(int L,int R){
    if(L==0||R==0) return L+R;
    if(tree[L].pri>tree[R].pri){
        tree[L].rs=Merge(tree[L].rs,R);
        update(L);
        return L;
    }
    else{
        tree[R].ls=Merge(L,tree[R].ls);
        update(R);
        return R;
    }
}
void insert(int x,int v){
    int L,R;
    split(root[v],x,L,R);
    newnode(x);
    int rp=Merge(L,cnt);
    root[++vers]=Merge(rp,R);
}
void del(int x,int v){
    int L,R,p;
    split(root[v],x,L,R);
    split(L,x-1,L,p);
    p=Merge(tree[p].ls,tree[p].rs);
    root[++vers]=Merge(Merge(L,p),R);
}
void rankx(int x,int v){
    int L,R;
    split(root[v],x-1,L,R);
    printf("%d\n",tree[L].size+1);
    root[++vers]=Merge(L,R);
}
void prinx(int p,int k){
    printf("%d\n",tree[findk(p,k)].key);
}
void prec(int x,int v){
    int L,R;
    split(root[v],x-1,L,R);
    if(!L) printf("-2147483647\n");
    else prinx(L,tree[L].size);
    root[++vers]=Merge(L,R);
}
void succ(int x,int v){
    int L,R;
    split(root[v],x,L,R);
    if(!R) printf("2147483647\n");
    else prinx(R,1);
    root[++vers]=Merge(L,R);
}
int main(){
    srand(time(NULL));
    scanf("%d",&n);
    while(n--){
        scanf("%d%d%d",&v,&op,&x);
        switch(op){
            case 1:insert(x,v);break;
            case 2:del(x,v);break;
            case 3:rankx(x,v);break;
            case 4:prinx(root[v],x);vers++;break;
            case 5:prec(x,v);break;
            case 6:succ(x,v);break;
        }
    }
    return 0;
}
2025/1/5 11:50
加载中...