HDU 4417 Super Mario（主席树区间不超过k的个数）题解

分手后的思念是犯贱 2021-12-20 04:53 215阅读 0赞

题意：问区间内不超过k的个数

思路：显然主席树，把所有的值离散化一下，然后主席树求一下小于等于k有几个就行。注意，他给你的k不一定包含在数组里，所以问题中的询问一起离散化。

代码：

#include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include <iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 1e5 + 10;
    const int M = maxn * 30;
    const ull seed = 131;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1000000007;
    int a[maxn], root[maxn], tot;
    int n, m;
    vector<int> vv;
    int getId(int x){
        return lower_bound(vv.begin(), vv.end(),x) - vv.begin() + 1;
    }
    struct node{
        int lson, rson;
        int sum;
    }T[maxn * 20];
    void init(){
        memset(T, 0, sizeof(T));
        tot = 0;
        vv.clear();
    }
    int lowbit(int x){
        return x&(-x);
    }
    void update(int l, int r, int &now, int pre, int v, int pos){
        T[++tot] = T[pre], T[tot].sum += v, now = tot;
        if(l == r) return;
        int m = (l + r) >> 1;
        if(m >= pos)
            update(l, m, T[now].lson, T[pre].lson, v, pos);
        else
            update(m + 1, r, T[now].rson, T[pre].rson, v, pos);
    }
    int query(int l, int r, int now, int pre, int v){
        if(l == r){
            if(v >= l)
                return T[now].sum - T[pre].sum;
            return 0;
        }
        if(r <= v)
            return T[now].sum - T[pre].sum;
        int m = (l + r) >> 1;
        int sum = 0;
        if(v < m){
            return query(l, m, T[now].lson, T[pre].lson, v);
        }
        else{
            sum = query(m + 1, r, T[now].rson, T[pre].rson, v);
            return T[T[now].lson].sum - T[T[pre].lson].sum + sum;
        }
    }
    struct ask{
        int l, r, k;
    }q[maxn];
    int main(){
        int T, ca = 1;
        scanf("%d", &T);
        while(T--){
            init();
            scanf("%d%d", &n, &m);
            for(int i = 1; i <= n; i++){
                scanf("%d", &a[i]);
                vv.push_back(a[i]);
            }
            for(int i = 1; i <= m; i++){
                scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
                q[i].l++, q[i].r++;
                vv.push_back(q[i].k);
            }
            sort(vv.begin(), vv.end());
            vv.erase(unique(vv.begin(), vv.end()), vv.end());
            for(int i = 1; i <= n; i++){
                update(1, vv.size(), root[i], root[i - 1], 1, getId(a[i]));
            }
            printf("Case %d:\n", ca++);
            for(int i = 1; i <= m; i++){
                printf("%d\n", query(1, vv.size(), root[q[i].r], root[q[i].l - 1], getId(q[i].k)));
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/KirinSB/p/10770755.html