POJ2104 —— K-th number

1、题目大意：区间第k小，什么修改没有。。。

2、分析：这个是可持久化线段树，也是主席树，解释一下，n个线段树是怎么存下的，就是每一颗线段树和前一个有logn个点不一样

然后我们只需要一个线段树开logn的空间，然后其他的指针指向上一个线段树对应的地方也是可以的对吧

然后。。然后就没了。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2000010], l[2000010];
pair<int , int> b[2000010];
int T[2000010], ls[2000010], rs[2000010];
int h[2000010];
int cnt[2000010];
int tot;
int num = 0;
inline int insert(int root, int pos){
    int nroot = ++ tot;
    int ret = nroot;
    int l = 1, r = num;
    cnt[nroot] = cnt[root] + 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(pos <= mid){
            r = mid;
            ls[nroot] = ++ tot;
            rs[nroot] = rs[root];
            nroot = ls[nroot];
            root = ls[root];
            cnt[nroot] = cnt[root] + 1;
        }
        else {
            l = mid + 1;
            ls[nroot] = ls[root];
            rs[nroot] = ++ tot;
            nroot = rs[nroot];
            root = rs[root];
        }
        cnt[nroot] = cnt[root] + 1;
    }
    return ret;
}
inline int query(int lll, int rrr, int k){
    int l = 1, r = num;
    int le_ = T[lll - 1];
    int ri_ = T[rrr];
    while(l < r){
        int mid = (l + r) / 2;
        int q = cnt[ls[ri_]] - cnt[ls[le_]];
        if(k <= q){
            r = mid;
            le_ = ls[le_];
            ri_ = ls[ri_];
        }
        else{
            l = mid + 1;
            k -= q;
            le_ = rs[le_];
            ri_ = rs[ri_];
        }
    }
    return l;
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        b[i] = make_pair(a[i], i);
    }
    sort(b + 1, b + n + 1);
    b[0].first = -2147483647;
    for(int i = 1; i <= n; i ++){
        if(b[i].first != b[i - 1].first) num ++;
        l[b[i].second] = num;
        h[num] = b[i].second;
    }
    T[0] = 1;
    tot = 1;
    for(int i = 1; i <= n; i ++) T[i] = insert(T[i - 1], l[i]);
    for(int i = 1; i <= m; i ++){
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", a[h[query(l, r, k)]]);
    }
    return 0;
}

巴特西

POJ2104 —— K-th number

最新文章

热门文章