树堆 样例过 全wa求教
查看原帖
树堆 样例过 全wa求教
567375
zgsankarea楼主2022/10/21 23:56

自己造了许多数与第一个题解对比没啥问题, 讨论区说的问题我也解决了但就是全wa求大佬看看。

代码
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<cstring>
#define maxn 1000019
#define INF 2147483647
using namespace std;
int n; //操作的个数;
int ch[maxn][2]; //树堆
int val[maxn]; //值
int more[maxn]; // 多余的
int prio[maxn]; // 关键值
int child[maxn];
int tot;
int root; //树根
int input1(){     //输入
    int sign = 1 ,out = 0;
    char s;
    s = getchar();
    while(s >'9' || s < '0'){
        sign = -1;
        s = getchar();
    }
    while(s <= '9' && s >='0'){
        out = out * 10 + s - '0';
        s = getchar();
    }
    return out * sign;
}

int new1(int v){      //新建节点
    val[++tot] = v;
    prio[tot] = rand();
    child[tot] = 1;
    more[tot] = 1;
    return tot;
}

void update(int id){     //更新节点的孩子数量便于之后按排名查找
    child[id] = child[ch[id][0]] + child[ch[id][1]] + more[id];
}

void build(){     // 建树
    root = new1(-INF);
    ch[root][1] = new1(INF);
    update(root);
}

void Rotate(int &id, int d){       //d = 0  左旋  1右旋
    int temp = ch[id][1^d];
    ch[id][1^d] = ch[temp][d];
    ch[temp][d] = id;
    id = temp;
    update(ch[id][d]);
    update(id);
}

void insert(int &id , int v){    //插入节点
    if(!id){
        id = new1(v);
        return;
    }
    if(val[id] == v){
        more[id]++;
    }
    else{
        int d = v > val[id]? 1:0;
        insert(ch[id][d],v);
        if(prio[ch[id][d]] > prio[id]){
            Rotate(id,1^d);
        }
    }
    update(id);
}


void remove(int &id , int v){   // 删除节点
    if(!id) return;
    if(val[id] == v){
        if(more[id] > 1){
            more[id]--;
            update(id);
            return;
        }
        if(ch[id][0] || ch[id][1]){
            if(!ch[id][1] || prio[ch[id][0]] > prio[ch[id][1]]){
                Rotate(id,1);
                remove(ch[id][1],v);
            }
            else{
                Rotate(id,0);
                remove(ch[id][0],v);
            }
            update(id);
        }
        else{
            id = 0;
        }
        return;
    }
    v< val[id] ? remove(ch[id][0],v):remove(ch[id][1],v);
    update(id);
}

int get_rank(int id,int v){
    if(!id) return 0;
    if(val[id] == v){
        return child[ch[id][0]]+1;
    }
    else if(val[id] >v){
        return get_rank(ch[id][0],v);
    }
    else{
        return child[ch[id][0]] + more[id] + get_rank(ch[id][1], v);
    }
}

int get_val(int id,int x){
    if(!id) return INF;
    if(x <= child[ch[id][0]]){
        return get_val(ch[id][0],x);
    }
    else if(x <= child[ch[id][0]] + more[id]){
        return val[id];
    }
    else{
        return get_val(ch[id][1],x - child[ch[id][0]] - more[id]);
    }
}
 

int get_next(int v){
    int id = root,next = 0;
    while(id){
        if(val[id] > v){
            next= val[id];
            id = ch[id][0];
        }
        else{
            id = ch[id][1];
        }
    }
    return next;
}



int get_pre(int v){
    int id = root ,pre = 0;
    while(id){
        if(val[id] < v){
            pre = val[id];
            id = ch[id][1];
        }
        else{
            id = ch[id][0];
        }
    }
    return pre;
}




int main(){
    build();
    int n = input1();
    for(int i = 1 ; i<= n ; i++){
        int order = input1();
        int num = input1();
        if(order == 1){
            insert(root, num);            //如果不存在该数则先插入(存在也先插入 对排名查找不影响)
            cout << get_rank(root,num) -1 << endl;   //查找
            remove(root,num);   // 删除
        }
        if(order == 2){
            if(num <=0){
                cout << INF << endl;
                continue;
            }
            cout << get_val(root,num+1) << endl;
        }
        if(order == 3){
            insert(root, num);
            cout << get_pre(num) << endl;
            remove(root,num);
        }
        if(order == 4){
            insert(root, num);
            cout << get_next(num)  << endl;
            remove(root,num);
        }
        if(order == 5){
            insert(root, num);
        }
    }
    return 0;
}
2022/10/21 23:56
加载中...