icontofig | 发布于 2017-01-06 17:56:04 | 阅读量 339 | splay
发布于 2017-01-06 17:56:04 | splay
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
const int INF = 2147483647;
struct splay_node{
    int value,siz,cnt;
    splay_node *pre,ch[2];
    void update(){
        siz = ch[0]->siz + ch[1]->siz + cnt;
    }
    int get_wh(){
        return pre->ch[0] == this ? 0 : 1;
    }
    void set_ch(int wh,splay_node *now);
}pool[maxn],*root,*null;
int top = 0;
splay_node get_new(int value){
    splay_node *now = pool + ++top;
    now->value = value;
    now->cnt = now->siz = 1;
    now->pre = now->ch[1] = now->ch[0] = null;
    return now;
}
inline splay_node::void set_ch(int wh,spaly_node *now){
    this->ch[wh] = now;
    if(now != null)now->pre = this;
    this->update();
    return;
}
inline void rotate(splay_node *&now){
    spaly_node *oldf = now->pre,*grand = now->pre->pre;
    int wh = now->get_wh();
    oldf->set_ch(wh,now->ch[wh^1]);
    now->set_ch(wh^1,oldf);
    now->pre = grand;
    if(grand != null)grand->ch[grand->ch[0] == oldf ? 0 : 1] = now;
    return;
}
inline void splay(splay_node *now,splay_node *tar){
    for(;now->pre != tar;rotate(now))
        if(now->pre->pre != tar)now->pre->get_wh() == now->get_wh() ? rotate(now->pre) : rotate(now);
    if(tar == null)root = now;
    return;
}
void insert(int value){
    splay_node *newone = get_new(value);
    splay_node *now = root;
    splay_node *last = null;
    while(now != null){
        last = now;
        if(newone->value == now->value){
            now->cnt++;
            now->siz += 1;
            splay(now,null)
            return;
        }
        if(newone->value < now->value)now = now->ch[0];
        else now = now->ch[1];
    }
    if(last == null)root = newone;
    else{
        if(newone->value < last->value)last->set_ch(0,newone);
        else last->set_ch(1,newone);
        splay(newone,null);
    }
    return;
}
inline splay_node *find(int value){
    splay_node *now = value;
    while(now != null){
        if(now->value == value)break;
        if(value < now->value)now = now->ch[0];
        else now = now->ch[1];
    }
    if(now != null)splay(now,null);
    return now;
}
void del(int value){
    splay_node *now = find(value);
    if(now == null)return;
    if(now->cnt > 1){
        now->cnt -= 1;
        now->siz -= 1;
        return;
    }
    if(now->ch[0] == null && now->ch[1] == null)root = null;
    else if(now->ch[1] == null){
        now->ch[0]->pre = null;
        root = now->ch[0];
    }
    else if(now->ch[0] == null){
        now->ch[1]->pre = null;
        root = now->ch[1];
    }
    else{
        splay_node *one = now->ch[0];
        while(one->ch[1] != null)one = one->ch[1];
        splay(one,now);
        one->set_ch(1,now->ch[1]);
        one->pre = null;
        root = one;
    }
    return;
}
inline int pre(int value){
    int ans = -INF;
    splay_node *now = root;
    while(now != null){
        if(now->value <= value){
            ans = max(ans,now->value);
            now = now->ch[1];
        }
        else now = now->ch[0];
    }
    return ans;
}
inline int nxt(int value){
    int ans = INF;
    splay_node *now = root;
    while(now != null){
        if(now->value >= value){
            ans = min(ans,now->value);
            now = now->ch[0];
        }
        else now = now->ch[1];
    }
    return ans;
}
inline int get_rank(int value){
    splay_node *now = root;
    int left_size = 0;
    while(now != null){
        if(value == now->value){
            int ans = left_size + now->ch[0]->siz + 1;
            splay(now,null);
            return ans;
        }
        if(value < now->value)now = now->ch[0];
        else left_size = left_size +now->ch[0] + cnt,now = now->ch[1];
    }
    return -1;
}
inline int kth(int k){
    int left_size = 0;
    splay_node *now = root;
    while(now != null){
        int kt = left_size + now->ch[0]->siz;
        if(kt+1 <= k && k <= kt + now->cnt){
            splay(now,null);
            return now->value;
        }
        if(k <= kt)now = now->ch[0];
        else{
            left_size += now->cnt;
            now = now->ch[1];
        }
    }
    return -1;
}
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
​

内容更新于: 2017-01-06 17:56:13
链接地址: http://blog.leanote.com/post/icontofig/be6355afdd99

上一篇: 【ZJOI2007】【BZOJ1058】报表统计splay+线段树

下一篇: [NOIP2016day1T2]running天天爱跑步

339 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航