树状数组之较复杂的区间统计（校长的问题）

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
/*代码是大佬的。*/
const int kMax = 1e5 + 10;

struct node{
    int a, b, ord, res;
    node(int _a, int _b, int _ord, int _res = 0) : 
        a(_a), b(_b), ord(_ord), res(_res) {}
};

int n;
int sum[kMax];

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

int getsum(int x) {//统计排名前x的人数
    int res = 0;
    for(;x;x -= lowbit(x)) {
        res += sum[x];
    }
    return res;
}

void add(int x) {
    for(;x <= n;x += lowbit(x)) {
        ++ sum[x];
    }
}

int num[kMax];
vector<node> table;

bool cmp(const node& a, const node& b) {//根据学号排名
    return a.a < b.a;
}

bool cmp_back(const node& a, const node& b) {//复原排名
    return a.ord < b.ord;
}

int main() {
    int m, a, b;
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n;++ i)//下标为学号，值为排名
        scanf("%d", &num[i]);
    int ord = 0;
    for(int i = 0;i < m;++ i) {//学号，排名
        scanf("%d%d", &a, &b);
        table.push_back({a, b, ord ++});//顺序
    }
    sort(table.begin(), table.end(), cmp);//排序
    int p = 0;
    for(int i = 0;i < m;++ i) {
        while(p < table[i].a) {//符合要求的学号
            add(num[p ++]);//以排名为起点，往后加1
        }
        table[i].res = getsum(table[i].b);//当前排名前有几人
    }
    sort(table.begin(), table.end(), cmp_back);//复原排名！！
    for(int i = 0;i < m;++ i) {
        printf("%d\n", table[i].res);
    }
    return 0;
}