换个角度思考

题意

每次查询区间里小于等于某个数的元素的个数，1e5范围

思路

离线操作，先对这组数排序，再对每个查询操作依据值排序，用树状数组更新及求和，每一次编号对应的值加一，从小到大计算不会出现错误。

错误点

• 貌似牛客int函数不写返回值会一直报段错误

占坑

其他dalao说是主席树模板题然而我并不会主席树

代码

#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 5;
int ans[maxn], sum[maxn];

struct node {
    int v, id;
}a[maxn];

struct node2 {
    int l, r, x, id;
}b[maxn];

int cmp(node x, node y) {
    // if(x.v == y.v) return x.id<y.id;
    return x.v < y.v;
}

int cmp2(node2 xx, node2 yy) {
    return xx.x < yy.x;
}

int n, m;

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

void update(int i, int k) { // pos i += k
    while (i <= n) {
        sum[i] += k;
        //        printf("pos %d += %d\n",i,k);
        i += lowbit(i);
    }
}

int getsum(int i) {
    int res = 0;
    while (i > 0) {
        res += sum[i];
        i -= lowbit(i);
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].v);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].x);
        b[i].id = i;
    }
    sort(b + 1, b + m + 1, cmp2);
    int i = 1, j = 1;
    for (i = 1; i <= m; i++) {
        while (b[i].x >= a[j].v && j <= n) {
            update(a[j].id, 1);
            j++;
        }
        ans[b[i].id] = getsum(b[i].r) - getsum(b[i].l - 1);
    }
    for (i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
}