< siomi sakaさんのAI生成コード置き場

treap? (クラウドで生成）

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

#include "stdlib.h"

#define TREAP_N 500005     // 総ノード数の上限
#define TREAP_MAX_TREES 1  // 同時に使う木の本数

typedef long long tkey_t;  // treapの型

// 比較関数(変更をわすれない)
static int tless(tkey_t a, tkey_t b){
    return a<b;
}



/**以下実装 */

typedef struct {
    tkey_t val;
    unsigned long long pri;
    int left, right, size; 
} TNode;

static TNode tnode[TREAP_N];
static int tfree[TREAP_N];   // eraseで空いたインデックスを再利用するスタック
static int tfree_top=0;
static int tcnt=1;         // 次に新規発行するインデックス(0はノードなし)

static int troot[TREAP_MAX_TREES]; 

static unsigned long long txorshift_state=88172645463325252ULL;

static unsigned long long txorshift(void){
    unsigned long long x=txorshift_state;
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    txorshift_state=x;
    return x;
}

// 乱数シードを変えるとき
void tseed(unsigned long long s){
    if(s==0){
        txorshift_state=1;
    }else{
        txorshift_state=s;
    }
}

static int tsize(int t){
    if(t==0){
        return 0;
    }else{
        return tnode[t].size;
    }
}

static void tupdate(int t){
    if(t==0) return;
    tnode[t].size=1+tsize(tnode[t].left)+tsize(tnode[t].right);
}

static int tnewnode(tkey_t val){
    int idx;
    if(0<tfree_top){
        idx=tfree[--tfree_top];
    } else {
        idx=tcnt++;
    }
    tnode[idx].val=val;
    tnode[idx].pri=txorshift();
    tnode[idx].left=0;
    tnode[idx].right=0;
    tnode[idx].size=1;
    return idx;
}


static void tsplit(int t, tkey_t key, int *l, int *r){
    if(t==0){ *l=0; *r=0; return; }
    if(tless(tnode[t].val, key)){
        tsplit(tnode[t].right, key, &tnode[t].right, r);
        *l=t;
    } else {
        tsplit(tnode[t].left, key, l, &tnode[t].left);
        *r=t;
    }
    tupdate(t);
}

static int tmerge(int l, int r){
    if(l==0) return r;
    if(r==0) return l;
    if(tnode[r].pri<tnode[l].pri){
        tnode[l].right=tmerge(tnode[l].right, r);
        tupdate(l);
        return l;
    } else {
        tnode[r].left=tmerge(l, tnode[r].left);
        tupdate(r);
        return r;
    }
}

static int terase_rec(int t, tkey_t val){
    if(t==0) return 0;
    if(!tless(tnode[t].val, val) && !tless(val, tnode[t].val)){ // val == tnode[t].val
        int merged=tmerge(tnode[t].left, tnode[t].right);
        tfree[tfree_top++]=t;
        return merged;
    } else if(tless(val, tnode[t].val)){
        tnode[t].left=terase_rec(tnode[t].left, val);
    } else {
        tnode[t].right=terase_rec(tnode[t].right, val);
    }
    tupdate(t);
    return t;
}

// tの部分木内でvalより小さいものの個数
static int tcount_less(int t, tkey_t val){
    if(t==0) return 0;
    if(tless(tnode[t].val, val)){
        return tsize(tnode[t].left)+1+tcount_less(tnode[t].right, val);
    } else {
        return tcount_less(tnode[t].left, val);
    }
}

/**mainで呼ぶ関数 */

/**id...使う階層,tkey_t val....あらたに挿入したいやつ */
void tinsert(int id, tkey_t val){
    int l, r;
    tsplit(troot[id], val, &l, &r);
    int node=tnewnode(val);
    troot[id]=tmerge(tmerge(l, node), r);
}

// 値valを1つだけ削除
void terase(int id, tkey_t val){
    troot[id]=terase_rec(troot[id], val);
}

// val未満の要素数
int tlower_bound(int id, tkey_t val){
    return tcount_less(troot[id], val);
}

// val以下の要素数
int tupper_bound(int id, tkey_t val){
    int t=troot[id];
    int result=0;
    while(t){
        if(tless(val, tnode[t].val)){
            t=tnode[t].left;
        } else {
            result+=tsize(tnode[t].left)+1;
            t=tnode[t].right;
        }
    }
    return result;
}

// valの個数
int tcount(int id, tkey_t val){
    return tupper_bound(id, val)-tlower_bound(id, val);
}

// 全要素数
int tall_size(int id){
    return tsize(troot[id]);
}

// 小さい方から0-indexedでk番目の値を取得
tkey_t tkth(int id, int k){
    int t=troot[id];
    while(t){
        int ls=tsize(tnode[t].left);
        if(k<ls){
            t=tnode[t].left;
        } else if(k==ls){
            return tnode[t].val;
        } else {
            k-=ls+1;
            t=tnode[t].right;
        }
    }
    return -1; // 範囲外
}

// 大きい方から0-indexedでk番目の値を取得
tkey_t tkth_from_back(int id, int k){
    int total=tall_size(id);
    if(k<0 || k>=total) return -1;
    return tkth(id, total-1-k);
}

// 全ての木をリセット
void tclear(void){
    for(int i=0;i<TREAP_MAX_TREES;i++) troot[i]=0;
    tcnt=1;
    tfree_top=0;
}