BZOJ1901——Zju2112 Dynamic Rankings

1、题目大意：区间第k小，有单点修改

2、分析：这个是树状数组套线段树，也是主席树。。。。为什么主席树这么多QAQ

就是树套树的那种插入什么的，注意啊，一定要动态开内存。。不然会爆。。

然后算答案有两种算法，一种是二分答案，然后算一下，另一种就是把logn棵线段树的指针都存一下，

然后再递归找第k大的时候，我们就可以暴力枚举这些指针，别忘了维护他们

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct segment{
    segment *ls, *rs;
    int num;
} *root[10010], ft[11000010];
int cnt;
int a[10010];
int n, m;
inline void tree_insert(segment* &p, int l, int r, int value){
    if(p == NULL) p = &ft[cnt ++];
    if(l == r){
        p -> num ++;
        return;
    }
    int mid = (l + r) / 2;
    if(value <= mid) tree_insert(p -> ls, l, mid, value);
    else tree_insert(p -> rs, mid + 1, r, value);
    p -> num = 0;
    if(p -> ls) p -> num += p -> ls -> num;
    if(p -> rs) p -> num += p -> rs -> num;
}
inline void tree_Delete(segment* &p, int l, int r, int value){
    if(p == NULL) p = &ft[cnt ++];
    if(l == r){
        p -> num --;
        return;
    }
    int mid = (l + r) / 2;
    if(value <= mid) tree_Delete(p -> ls, l, mid, value);
    else tree_Delete(p -> rs, mid + 1, r, value);
    p -> num = 0;
    if(p -> ls) p -> num += p -> ls -> num;
    if(p -> rs) p -> num += p -> rs -> num;
}
inline int tree_lessk(segment* &p, int l, int r, int value){
    if(!p) return 0;
    if(l == r) return p -> num;
    int mid = (l + r) / 2;
    int ret = 0;
    if(value <= mid) ret += tree_lessk(p -> ls, l, mid, value);
    else {
        if(p -> ls) ret += p -> ls -> num;
        ret += tree_lessk(p -> rs, mid + 1, r, value);
    }
    return ret;
}
inline void insert(int x, int y){
    for(; x <= n; x += (x & -x))
        tree_insert(root[x], 0, 1000000000, y);
}
inline void Delete(int x, int y){
    for(; x <= n; x += (x & -x))
        tree_Delete(root[x], 0, 1000000000, y);
}
inline int lessk(int x, int y){
    int ret = 0;
    for(; x > 0; x -= (x & -x))
        ret += tree_lessk(root[x], 0, 1000000000, y);
    return ret;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        insert(i, a[i]);
    }
    char str[2];
    int x, y, z;
    for(int i = 1; i <= m; i ++){
        scanf("%s", str);
        scanf("%d%d", &x, &y);
        if(str[0] == 'Q'){
            scanf("%d", &z);
            int l = 0, r = 1000000000;
            while(l < r){
                int mid = (l + r) / 2;
                if(lessk(y, mid) - lessk(x - 1, mid) >= z) r = mid;
                else l = mid + 1;
            }
            printf("%d\n", l);
        }
        else{
            Delete(x, a[x]);
            a[x] = y;
            insert(x, a[x]);
        }
    }
    return 0;
}

巴特西

BZOJ1901——Zju2112 Dynamic Rankings

最新文章

热门文章