icontofig | 发布于 2017-04-06 00:00:14 | 阅读量 165 | splay 线段树 树套树
发布于 2017-04-06 00:00:14 | splay 线段树 树套树

引言

好久没写题解了,正好不怎么想写代码,还是来发波题解吧。

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数

题解

这是一道线段树套平衡树(就是每个线段树节点里面都存着一颗平衡树)的裸题。。。
用线段树维护下标区间,然后把平衡树节点套到线段树节点里面,注意此处的平衡树节点维护的是权值的大小。 修改操作可以转化成为找到当前这个数对应的区间,在splay里面删掉这个数,然后插入修改成的那个数就OK。
然后就是注意排名的话是比当前小的数的个数+1。
要求区间内排名为k的数的时候,我们就得注意了。因为我们是线段树套平衡树,所以说查询区间的时候,查询区间会分布在很多个线段树节点上。所以这样的话,这个操作就只能是二分答案,然后去看答案的排名是不是在这个查询区间中排k。(注意因为有重复的数,所以要求最大排名和最小排名,看k是不是在这个范围内)。
最后要注意的就是……为了保证空间,一律用内存池写。(可能我的代码里面的指针对某些读者不太友善。。。)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
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;
}
const int maxn = 5e4+5;
const int lg = 30;
const int INF = 2147483647;
int a[maxn],n,m,x,y,z;
struct splay_node{
    splay_node *pre,*ch[2];
    int siz,cnt,v;
    void update();
    int get_wh();
    void set_ch(int wh,splay_node *child);
}pool[maxn*lg],*null;
int top = 0;
int splay_node::get_wh(){
    return pre->ch[0] == this ? 0 : 1;
}
void splay_node::update(){
    siz = ch[0]->siz + ch[1]->siz + cnt;
}
void splay_node::set_ch(int wh,splay_node *child){
    ch[wh] = child;
    if(child != null)child->pre = this;
    update();
}
splay_node *get_new(int value){
    splay_node *newone = pool + ++top;
    newone->siz = newone->cnt = 1;
    newone->pre = newone->ch[0] = newone->ch[1] = null;
    newone->v = value;
    return newone;
}
struct segment{
    segment *lc,*rc;
    int l,r;
    splay_node *root;
    void rotate(splay_node *&now){
        splay_node *fa = now->pre,*grand = now->pre->pre;
        int wh = now->get_wh();
        fa->set_ch(wh,now->ch[wh^1]);
        now->set_ch(wh^1,fa);
        now->pre = grand;
        if(grand != null)
            grand->ch[grand->ch[0] == fa ? 0 : 1] = now; 
    }
    void splay(splay_node *now,splay_node *tar){
        for(;now->pre != tar;rotate(now))
            if(now->pre->pre != tar)now->get_wh() == now->pre->get_wh() ? rotate(now->pre) : rotate(now);
        if(tar == null)root = now; 
    }
    void insert(int pos){
        splay_node *now = root;
        splay_node *last = now;
        while(now != null){
            last = now;
            if(now->v == a[pos]){
                now->cnt++;
                now->siz++;
                splay(now,null);
                return;
            }
            else if(now->v < a[pos])now = now->ch[1];
            else now = now->ch[0];
        }
        if(last == null)root = get_new(a[pos]);
        else{
            splay_node *newone = get_new(a[pos]);
            last->set_ch(last->v < newone->v ? 1 : 0,newone);
            splay(newone,null);
        }
        return;
    }
    splay_node *find(splay_node *now,int value){
        if(now->v == value)return now;
        else if(now->v < value)return find(now->ch[1],value);
        else return find(now->ch[0],value);
    }
    void del(int value){
        splay_node *now = find(root,value);
        splay(now,null);
        if(now->cnt > 1){
            now->siz -= 1;
            now->cnt -= 1;
            return;
        }
        if(now->ch[0] == null && now->ch[1] == null)root = null;
        else if(now->ch[0] == null && now->ch[1] != null){
            now->ch[1]->pre = null;
            root = now->ch[1];
            return;
        }
        else if(now->ch[1] == null && now->ch[0] != null){
            now->ch[0]->pre = null;
            root = now->ch[0];
            return;
        }
        else{
            splay_node *tar = now->ch[0];
            while(tar->ch[1] != null)tar = tar->ch[1];
            splay(tar,now);
            tar->set_ch(1,now->ch[1]);
            tar->pre = null;
            root = tar;
            return;
        }
    }
    void get_splay(){
        root = null;
        insert(0);
        for(int i = l;i <= r;++i)insert(i);
        return;
    }
    int get_pre(int value){
        splay_node *now = root;
        int ret = -INF;
        while(now != null){
            if(now->v >= value)now = now->ch[0];
            else{
                ret = now->v;
                now = now->ch[1];
            }
        }
        return ret;
    }
    int get_next(int value){
        splay_node *now = root;
        int ret = INF;
        while(now != null){
            if(now->v <= value)now = now->ch[1];
            else{
                ret = now->v;
                now = now->ch[0]; 
            }
        }
        return ret;
    }
    void get_rank(int value,int &lr,int &rr){
        splay_node *now = root;
        while(now != null){
            if(now->v == value){
                lr += now->ch[0]->siz;
                rr += now->cnt + now->ch[0]->siz;
                break;
            }
            else if(now->v > value)now = now->ch[0];
            else{
                lr += now->ch[0]->siz + now->cnt;
                rr += now->ch[0]->siz + now->cnt;
                now = now->ch[1];
            }
        }
        return;
    }
}nil[maxn<<2],*nul,*rot;
int tot = 0;
void init(){
    null = pool;
    null->pre = null->ch[0] = null->ch[1] = null;
    null->v = null->siz = null->cnt = 0;
    nul = nil;
    nul->l = nul->r = 0;
    nul->lc = nul->rc = nul;
    nul->root = null;
    rot = nul;
}
segment *build(int l,int r){
    segment *now = nil + ++tot;
    now->l = l;now->r = r;
    now->lc = now->rc = nul;
    now->get_splay();
    if(l == r)return now;
    int mid = (l + r) >> 1;
    now->lc = build(l,mid);
    now->rc = build(mid+1,r);
    return now;
}
void update(segment *now,int pos,int pre_value){
    now->del(pre_value);
    now->insert(pos);
    if(now->l == now->r)return;
    int mid = (now->l + now->r) >> 1;
    if(pos <= mid)update(now->lc,pos,pre_value);
    else if(pos > mid)update(now->rc,pos,pre_value);
    return;
}
int query_pre(segment *now,int l,int r,int value){
    if(now->l >= l && now->r <= r)
        return now->get_pre(value);
    int mid = (now->l + now->r) >> 1;
    int ret = -INF;
    if(l <= mid)ret = max(ret,query_pre(now->lc,l,r,value));
    if(r > mid)ret = max(ret,query_pre(now->rc,l,r,value));
    return ret;
}
int query_next(segment *now,int l,int r,int value){
    if(now->l >= l && now->r <= r)
        return now->get_next(value);
    int mid = (now->l + now->r) >> 1;
    int ret = INF;
    if(l <= mid)ret = min(ret,query_next(now->lc,l,r,value));
    if(r > mid)ret = min(ret,query_next(now->rc,l,r,value));
    return ret;
}
void query_rank(segment *now,int l,int r,int value,int &rank1,int &rank2){
    if(now->l >= l && now->r <= r){
        now->get_rank(value,rank1,rank2);
        return;
    }
    int mid = (now->l + now->r) >> 1;
    if(l <= mid)query_rank(now->lc,l,r,value,rank1,rank2);
    if(r > mid)query_rank(now->rc,l,r,value,rank1,rank2);
    return;
}
void solve(int l,int r,int k){
    int rank1 = 0,rank2 = 0;
    int L = 0,R = 1e8,mid = 0;
    while(L <= R){
        mid = (L + R) >> 1;
        rank1 = rank2 = 0;
        query_rank(rot,l,r,mid,rank1,rank2);
        rank1 += 1;
        if(k >= rank1 && k <= rank2)break;
        if(k < rank1)R = mid - 1;
        else if(k > rank2)L = mid + 1; 
    }
    printf("%d\n",mid);
    return;
}
int opt;
int main(){
    init();
    n = get_num();
    m = get_num();
    for(int i = 1;i <= n;++i)
        a[i] = get_num();
    a[0] = INF;
    rot = build(1,n);
    while(m--){
        opt = get_num();
        if(opt == 3){
            x = get_num();y = get_num();
            z = a[x];
            a[x] = y;
            update(rot,x,z);
            continue;
        }
        x = get_num();y = get_num();z = get_num();
        if(opt == 1){
            int rank1 = 0,rank2 = 0;
            query_rank(rot,x,y,z,rank1,rank2);
            printf("%d\n",rank1+1);
            continue; 
        }
        if(opt == 2){
            solve(x,y,z);
            continue;
        }
        if(opt == 4){
            printf("%d\n",query_pre(rot,x,y,z));
            continue;
        }
        if(opt == 5){
            printf("%d\n",query_next(rot,x,y,z));
        }
    }
    return 0;
}​



内容更新于: 2017-04-06 00:00:14
链接地址: http://blog.leanote.com/post/icontofig/dbc40b964f78

上一篇: SDOI 2017 R1(这不是题解再说一遍)

下一篇: FFT模板 【UOJ】模板题库 多项式乘法

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