nowcoder NC19427 换个角度思考（离线树状数组）

题目链接：https://ac.nowcoder.com/acm/problem/19427

题意：给你$n$n个数，$m$m次查询，每次查询$[l,r]$[l,r]范围内比$x$x小的数的个数。

思路：隔了两个月就把离线树状数组忘得一干二净啦
这一题就是一道很典型得离线树状数组的题，我们可以把所有的数按从小到大排序，并将查询按$x$x从小到大排序，之后就遍历每次查询，更新树状数组的直接好啦。

AC代码：

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
#define pii pair<int,int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define rep(i,a,b) for(int i = (a) ; i <= (b) ; i++)
#define per(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define mem(a) memset(a,0,sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define fast_io ios::sync_with_stdio(false)

const int INF = 1e9 + 10;
const LL mod = 2019;
const int maxn = 2e5 + 7;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * f;
}

int head[maxn << 1];
struct Edge {
    int to, next;
}edge[maxn << 1];
int tot;

void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

void addedge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

int c[maxn];

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

void update(int x,int y,int n) {
    for(int i = x ; i <= n ; i += lowbit(i)) {
        c[i] += y;
    }
}

int query(int x,int n) {
    int ans = 0;
    for(int i = x ; i ; i -= lowbit(i)) {
        ans += c[i];
    }
    return ans;
}

LL qpow(LL a, LL b, LL p) {
    LL res = 1;
    while (b) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

pii a[maxn];

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

bool cmp(node aa,node bb) {
    return aa.x < bb.x;
}

int ANS[maxn];

int main() {
    int n,m;
    sd(n),sd(m);
    rep(i,1,n) {
        sd(a[i].first);
        a[i].second = i;
    }
    rep(i,1,m) {
        sd(b[i].l),sd(b[i].r),sd(b[i].x);
        b[i].id = i;
    }

    sort(a+1,a+n+1);
    sort(b+1,b+m+1,cmp);
    int pos = 1;
    rep(i,1,m) {
        while(a[pos].first <= b[i].x && pos <= n) {
            update(a[pos].second,1,n);
            pos++;
        }
        int ans = query(b[i].r,n) - query(b[i].l-1,n);
        ANS[b[i].id] = ans;
    }
    rep(i,1,m) pd(ANS[i]);
    return 0;
}