HDU4417 Super Mario 主席树

😊 | Powered By HeartFireY

Problem Analysis

题目大意：给定一个长度为 n n n的整数序列以及 m m m组询问，对于每组询问给出的 L , R , H L,R,H L,R,H，回答区间 [ L , R ] [L,R] [L,R]内不大于 H H H的数字的个数。也就是求区间内小于等于 H H H的数字的个数。

给定整数序列+区间查询，考虑用主席树解决。建立权值数组，对每个节点维护一颗主席树。查询为单点查询，查询数字对应的权值数组的个数。然后对于每个询问，在区间内二分枚举所有可能的数字 k k k，求一个满足 k ≤ h k \leq h k≤h的最大 k k k。就是我们想要得到的答案。

Accepted Code

#include 
#define ll long long
using namespace std;

const int N = 1e5 + 10;

ll root[N], sum[N  t;
    while(t--){
        ll n, m; cin >> n >> m;
        for(int i = 1; i > a[i]; b[i] = a[i];
        }
        sort(b + 1, b + 1 + n);
        ll sz = unique(b + 1, b + 1 + n) - b - 1;
        for(int i = 1; i