RE : End of a Dream

评测记录

代码在本地测试样例有时 RE 有时能正常跑完。自认为码风良好。

代码如下：

// #pragma GCC optimize(2) // 开启O2优化
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define INF 0x3f3f3f3f // 无穷大
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define func function<void()>
random_device rd;
mt19937 gen(rd());
inline int getRand(const int &st,const int &ed){//随机数函数
	uniform_int_distribution<> distrib(st,ed);
	return distrib(gen);
}
namespace treap{
    struct node{
        node *lson = nullptr,*rson = nullptr;
        int val;// 键值
        int pri;// 优先值
        int sze;// 大小
    }*root;
    inline int get(node *idx){
        if(idx == nullptr)return 0;
        return idx->sze;
    }
    inline void push_up(node *idx){
        if(idx == nullptr)return ;
        node &now = *idx;
        now.sze = get(now.lson) + get(now.rson) + 1;
    }
    void split(node *idx,const int &x,node *&L,node *& R){
//        printf("split x = %d idx => %d\n",x,idx);
        if(idx == nullptr){
            L = nullptr,R = nullptr;
            return ;
        }
        node &now = *idx;
        if(now.val <= x)L = idx,split(now.rson,x,now.rson,R);
        else R = idx,split(now.lson,x,L,now.lson);
        push_up(idx);
    }
    // 合并操作
    node * merge(node *L,node *R){
//        printf("merge\n");
        if(L == nullptr)return R;
        else if(R == nullptr)return L;
        node &lnow = *L,&rnow = *R;
        if(lnow.pri > rnow.pri){
            // 合并右子树
            lnow.rson = merge(lnow.rson,R);
            push_up(lnow.rson);
            return L;
        }else{
            // 合并左子树
            rnow.lson = merge(L,rnow.lson);
            push_up(rnow.lson);
            return R;
        }
    }
    // 把 x 添加进去
    void insert(const int &x){
        node *idx = new node;
        node &toput = *idx;
        toput.pri = getRand(0,1e9);
        toput.val = x,toput.sze = 1;
        node *lp,*rp;
        split(root,x,lp,rp);
        root = merge(merge(lp,idx),rp);
    }
    void erase(const int &x){
        node *lp,*mp,*rp;
        split(root,x,lp,rp);
        split(lp,x-1,lp,mp);
        mp = merge(mp->lson,mp->rson);
        root = merge(merge(lp,mp),rp);
    }
    // 求排名
    int getrank(const int &x){
        // 小于
        node *lp,*rp;
        split(root,x-1,lp,rp);
        int ans = lp->sze + 1;
        root = merge(lp,rp);
        return ans;
    }
    // 查询排名为 k 的值
    int kth(node *idx,const int &k){
        node &now = *idx;
//        printf("kth now = %d k = %d now.sze = %d get(now.lson) = %d now.val = %d\n",idx,k,now.sze,get(now.lson),now.val);
        // 如果正好是
        if(get(now.lson) == k - 1)return now.val;
//        printf("gett\n");
        if(get(now.lson) >= k)return kth(now.lson,k);
        else kth(now.rson,k - get(now.lson) - 1);
    }
    // x 的前趋
    int pre(const int &x){
        node *lp,*rp;
        split(root,x-1,lp,rp);
        int ans = kth(lp,lp->sze);
//        printf("ans gotton.\n");
        root = merge(lp,rp);
        return ans;
    }
    // x 的后继
    int suc(const int &x){
        node *lp,*rp;
        split(root,x,lp,rp);
        int ans = kth(rp,1);
        root = merge(lp,rp);
        return ans;
    }
}
using namespace treap;
int n,op,x;

// 输入函数
void input(){
    scanf("%d",&n);
//    insert(INT_MIN),insert(INT_MAX);
}

// 处理函数
void solve(){
    while(n--){
        scanf("%d%d",&op,&x);
        if(op == 1){
            insert(x);
        }else if(op == 2){
            erase(x);
        }else if(op == 3){
            printf("%d\n",getrank(x));
        }else if(op == 4){
            printf("%d\n",kth(root,x));
        }else if(op == 5){
            printf("%d\n",pre(x));
        }else if(op == 6){
            printf("%d\n",suc(x));
        }
    }
}

// 输出函数
void output(){

}

// 主函数
int main(int argc,char* argv[]){
	input();
	solve();
	output();
	return 0;
}