Question

给定一个长为的数组，对其求次询问，每次求。

Solution

离线+树状数组
这里该如何用树状数组表示是个问题，一开始我的想法是多开树状数组，显然必TLE，这里要结合离线。
我们把输入的数组，存为形式，其中放值，放对应的位置。
我们将输入的询问放入中，按照询问的从小到大排序。
这样排序的好处是，我们维护树状数组时，维护到则停下来，则当前答案就为所求答案，然后继续重复这种操作，答案的记录保存的位置和询问输入的顺序要一致。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

struct node{
    int l,r,x,id;
    bool operator < (const node & T) const{
        return x<T.x;
    }
}t[N];

int n,m;
pair<int,int>a[N];
int tree[N];
int ans[N];
inline int lowbit(int x){return x&-x;}

inline void add(int x){
    while(x<=n){
        tree[x]++;
        x+=lowbit(x);
    }
}

inline int ask(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=tree[x];
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i].fi,a[i].se=i;
    for(int i=1;i<=m;i++) cin>>t[i].l>>t[i].r>>t[i].x,t[i].id=i;
    sort(a+1,a+1+n);
    sort(t+1,t+1+m);
    for(int i=1,k=1;i<=m;i++){
        while(k<=n && a[k].fi<=t[i].x) add(a[k].se),++k;
        ans[t[i].id]=ask(t[i].r)-ask(t[i].l-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}