【每日一题】换个角度思考

戳我传送
题意：

思路：
离线+值域树状数组，保存每个点和每次询问的编号，每个点按照值的大小升序排序，每次询问按照k值大小升序排序。
原理：
1.处理k1的答案时（k最小的询问），树状数组中小于k1的位置都会被1标记，k1的答案就是树状数组 [l,r] 中1的个数。
2.处理k2时（k2>=k1），之前被1标记的位置的数都是小于等于k2的，不需要从头标记，只要继续找还有没有小于等于k2的数，标记它的位置就可以了。
3.后面每次询问重复1、2步骤，最多只要标记n个点。
4.每个点升序排序方便找小于等于k的数。
5.复杂度 。
Code：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
struct Query{
    int l,r,k;
    int id;
    bool operator<(const Query&a)const{
        return k<a.k;
    }
}q[maxn];
struct node{
    int id,val;
    bool operator<(const node&a)const{
        return val<a.val;
    }
}a[maxn];
int ans[maxn],sum[maxn],n,m;
#define lowbit(x) (x&-x)
void add(int x) {
    while(x<=n) {
        sum[x]+=1;
        x+=lowbit(x);
    }
}
int query(int x) {
    int ans=0;
    while(x) {
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() {
    read(n),read(m);
    for(int i=1;i<=n;++i) {
        read(a[i].val);
        a[i].id=i;
    }
    for(int i=1;i<=m;++i) {
        read(q[i].l),read(q[i].r),read(q[i].k);
        q[i].id=i;
    }
    sort(a+1,a+1+n);
    sort(q+1,q+1+m);
    for(int i=1,j=1;i<=m;++i) {
        int k=q[i].k;
        for(;j<=n&&a[j].val<=k;++j) add(a[j].id);
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}