Treap 60分求调
查看原帖
Treap 60分求调
109689
charain楼主2021/11/30 11:14

蒟蒻调了2天了QwQ,第6组数据其中一个求排名的数据有错(我是617,答案616

#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <pthread.h>
#include <bits/stdc++.h>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
//#include "file2.h"
using namespace std;
const int maxn=1005;

struct Node{
    Node *child[2];//子节点
    int r,v;        //r为优先级,v为键值
    int s;          //节点总数
    Node (int v):v(v){child[0]=child[1]=NULL;r=rand();s=1;}
};


void maintain(Node* &o){//同线段树一样的整理函数
    o->s=1;             //用到更新子节点的地方便应该整理一次
    if(o->child[0]!=NULL)o->s+=o->child[0]->s;
    if(o->child[1]!=NULL)o->s+=o->child[1]->s;
}
//d=0代表左旋,d=1代表右旋          
void Rotate(Node* &o,int d){//向那一边旋转,根节点便会被下放到那一边
    Node* k=o->child[d^1];o->child[d^1]=k->child[d];k->child[d]=o;
    maintain(o);maintain(k);o=k;//先整理o,后整理k
}
void Insert(Node* &o,int x){//插入节点函数
    if(o==NULL)o=new Node(x);   //没有便新建一个
    else{
        int d=(x<o->v?0:1);     //选择方向
        Insert(o->child[d], x);
        if(o->r < o->child[d]->r)Rotate(o, d^1);
    }   //子节点优先级更高,根下放到低优先级一侧,让为给高优先级
    maintain(o);
}
void Remove(Node* &o,int x){//删除节点函数
    if(o->v==x){//找到啦!
        if(o->child[0]==NULL)o=o->child[1];//如果只找到了一个节点,那么替换掉
        else if(o->child[1]==NULL)o=o->child[0];
        else{   //选择优先级低的那一边
            int d=(o->child[0]->r < o->child[1]->r?0:1);
            Rotate(o, d);//将根节点下放到底优先级那一边
            Remove(o->child[d],x);//对底优先级一侧删除
            //maintain(o);
        }
    }   //没找到,去子节点找
    else if(o->v<x)Remove(o->child[1], x);
    else Remove(o->child[0], x);
    if(o!=NULL)maintain(o);
}
bool Find(Node* o,int x){//寻找节点,注意根节点并未引用
    while(o!=NULL){ //一直找到无法找到
        if(o->v == x)return true;//找到啦!
        int d=(o->v>x?0:1);
        o=o->child[d];  //没找到,接着找
    }
    return false;//没找到。
}

int Value(Node* o,int k){//这里的k值表示在以当前节点为根的情况下的排名
    if(o==NULL or k<=0 or k>o->s)return 0;//找不到
    int now_rank=(o->child[0]==NULL?1:o->child[0]->s+1);//寻找当前节点排名
    if(now_rank==k)return o->v;//找到啦!
    else if(k<now_rank)return Value(o->child[0], k);
    else return Value(o->child[1], k-now_rank);
}
int Rank(Node* o,int v){
    if(o==NULL)return 0;
    int now_rank=(o->child[0]==NULL?1:o->child[0]->s+1);//寻找当前节点排名
    if(o->v==v)return now_rank;
    else if(o->v<v)return now_rank+Rank(o->child[1], v);
    else return Rank(o->child[0], v);
}
int Find_pre(Node* o,int v){
    int pre_num;
    while (o!=NULL) {
        if(o->v<v)pre_num=o->v,o=o->child[1];
        else o=o->child[0];
    }
    return pre_num;
}
int Find_next(Node* o,int v){
    int next_num;
    while (o!=NULL) {
        if(o->v>v)next_num=o->v,o=o->child[0];
        else o=o->child[1];
    }
    return next_num;
}

Node* root=new Node(0x7fffffff);

int main(){
    freopen("output","w",stdout);
    freopen("input","r",stdin);
    
    int n;
    int opt,val;
    scanf("%d",&n);
    while (n--) {
        scanf("%d%d",&opt,&val);
        if(opt==1)Insert(root, val);
        else if(opt==2)Remove(root, val);
        else if(opt==3)printf("获得排名%d :%d\n",Rank(root, val),val);
        else if(opt==4)printf("获得值%d\n",Value(root, val));
        else if(opt==5)printf("找前驱%d\n",Find_pre(root, val));
        else printf("找后继%d\n",Find_next(root, val));

    }

    return 0;
}
2021/11/30 11:14
加载中...