【每日一题】换个角度思考 (树状数组+离线 / 区间问题)

Solution
题意：给出一个数列，针对每个L,R,X 的区间求 [ L, R ] 中小于等于 x 的个数。

区间 个数 很容易想到树状数组来维护
考虑 离线处理问题
pair 存储数列的元素内容和索引 然后按照从小到大排序
然后再对 存储询问的结构体 按 x 的值 从小到大排序

以上的前戏做完，就可以计算每个区间的答案了：
遍历 pair ， 因为 pair 中的元素是递增的 且 结构体也是按 x 递增的 ， 所以前一个询问的答案也是后一个询问的答案一部分， 依次遍历 单点更新 区间求和。

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;

struct node{
    ll l,r,x,id;
}a[manx];
bool cmp(node a ,node b){
    return a.x<b.x;
}
pair<ll,ll>b[manx];
ll c[manx],ans[manx];
ll n,m;

void add(ll x){
    while(x<=n){
        c[x]++;
        x+= x&(-x);
    }
}
ll gets(ll x){
    ll ans=0;
    while(x){
        ans+=c[x];
        x-= x&(-x);
    }
    return ans;
}
int main(){
    io;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>b[i].fi,b[i].se=i;
    for(int i=1;i<=m;i++) cin>>a[i].l>>a[i].r>>a[i].x,a[i].id=i;
    sort(a+1,a+1+m,cmp);
    sort(b+1,b+1+m);
    for(int i=1,k=1;i<=m;i++){
        while(k<=n&&b[k].fi<=a[i].x) add(b[k].se),++k;
        ans[a[i].id]=gets(a[i].r)-gets(a[i].l-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}