AcWing 789. 数的范围

原题链接：https://www.acwing.com/problem/content/description/791/

思路一：二分查找

用两个二分查找，一个查找target的左边界，一个查找右边界。

#include <iostream>
#include <cstring>

#define LL long long
#define N 100005
#define Q 10005
#define K 10005


int ans[Q][2], nums[N];

int bin_search_r(int nums[], int left, int right, int target) {
    int i = left, j = right;
    
    while (i < j) {
        int k = (i + j) >> 1;
        if (nums[k] < target) i = k + 1;
        else if (target < nums[k]) j = k;
        else {
            if (j - i == 1) return k;
            i = k;
        }
        // printf("%d %d\n", i, j);
    }
    return -1;
}

int bin_search_l(int nums[], int left, int right, int target) {
    int i = left, j = right;
    
    while (i < j) {
        int k = (i + j) >> 1;
        if (nums[k] < target) i = k + 1;
        else if (target < nums[k]) j = k;
        else {
            if (j - i == 1) return k;
            j = k;
        }
    }
    if (nums[i] == target) return i;
    return -1;
}



int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    int tmp;
    for (int i = 0; i < q; i++) {
        scanf("%d", &tmp);
        int l = bin_search_l(nums, 0, n, tmp);
        int r = bin_search_r(nums, 0, n, tmp);
        ans[i][0] = l; ans[i][1] = r;
    }
    for (int i = 0; i < q; i++) {
        printf("%d %d\n", ans[i][0], ans[i][1]);
    }
    
    
    return 0;
    
}

思路二：前缀和

由于题目给出了范围，我们只需要用一个count数组记录一下每个数出现了几次，然后可以用前缀和的思想，查询该数字的区间。

前缀和数组：

• 构造复杂度
• 查询复杂度
• 更新复杂度

思路三：树状数组

树状数组：

• 构造复杂度
• 查询复杂度
• 更新复杂度

#include <iostream>
#include <cstring>

#define LL long long
#define N 100005
#define Q 10005
#define K 10005


int ans[Q][2], count[K], sum[K];

int max_n; // 表示树状数组的长度   

int lowbit(int x) { return x & (-x); }

int getSum(int n) {
    if (n > max_n) n = max_n - 1;
    int res = 0;
    for (int i = n; i > 0; i -= lowbit(i)) {
        res += sum[i];
    }
    return res;
}

void build() {
    // 从头到尾填充树状数组
    for (int i = 1; i < max_n; i++) {
        sum[i] += count[i-1];
        int parent = i + lowbit(i);
        if (parent < max_n) sum[parent] += sum[i];
    }
    
}

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    
    int tmp, max = 0;
    memset(count, 0, sizeof count);
    memset(sum, 0, sizeof sum);
    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        count[tmp]++;
        if (tmp > max) max = tmp;
    }
    max_n = max + 2;
    build();
    for (int i = 0; i < q; i++) {
        scanf("%d", &tmp);
        if (count[tmp] == 0) {
            ans[i][0] = ans[i][1] = -1;
        }
        else {
            ans[i][0] = getSum(tmp);
            ans[i][1] = ans[i][0] + count[tmp] - 1;
        }
    }
    for (int i = 0; i < q; i++) {
        printf("%d %d\n", ans[i][0], ans[i][1]);
    }
    
    
    return 0;
    
}