一个比较裸的题目吧。

题目大意：
给n个数m次询问。每次询问一个区间[l,r]和一个数k，问区间[l,r]中小于等于k的数字个数。
n,m<=10^5，a[i]<=10^5

思路：
直接暴力查找肯定是不可行的。直接开桶的话，空间上也不允许。
但是我们可以分块。
把n个数分成n/sqrt(n)个块，每个块里sqrt(n)个数。最后一个块可能不足sqrt(n)个。
然后对每个块里的数字进行统计。由于n<=10^5，最多分出sqrt(10^5)=320个块左右。
那么我们可以开一个数组c[320][100040]表示第i个块中数字j出现了多少次,从时间和空间上都是开的下的。
统计完以后我们可以再for一遍把c数组变成一个前缀和数组，处理完以后我们的c[i][j]就变成了第i个块中小于等于数字j的数字个数。
剩下的就是直接查询了，由于我们已经预处理出前缀和数组。那么我们可以直接在线解决每一次的查询问题。计算出l和r所在的块，然后中间的直接按块跳过去，两个边界部分我们可以暴力计算。
这样做的复杂度就是m3sqrt(n)，跑了500ms。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int block;
int a[100040],c[330][100020];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    block=n/sqrt(n);
    int t=sqrt(n);
    for(int i=1;i<=n;i++){
        int b=(i-1)/t;
        c[b][a[i]]++;
    }
    for(int i=0;i<block;i++){
        for(int j=1;j<=100000;j++){
            c[i][j]+=c[i][j-1];
        }
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        int b1,b2;
        b1=(l-1)/t;
        b2=(r-1)/t;
        int tot=0;
        if(b1==b2){
            for(int i=l;i<=r;i++){
                if(a[i]<=k)tot++;
            }
        }
        else {
            for(int i=l;i<=(b1+1)*t;i++){
                if(a[i]<=k)tot++;
            }
            if(b1<b2){
                for(int i=b1+1;i<b2;i++){
                    tot+=c[i][k];
                }
            }
            for(int i=b2*t+1;i<=r;i++){
                if(a[i]<=k)tot++;
            }
        }

        cout<<tot<<endl;
    }
    return 0;
}

题目叫做“换个角度思考”，除了在线解决，要换个角度的话，就是离线了。
再来看看离线的方法， 本题显然是可以离线的。看到题目的时候感觉可能可以用莫队来做，不过我不会莫队
还是用树状数组吧！简单易懂。
对于[l,r]的区间查询问题，我们可以转化成求[1,r]-[1,l-1]的问题。而树状数组可以在logn时间内解决这个问题。但是我们其实希望在查询[l,r]的时候，[1,r]-[1,l-1]里的结果是满足小于等于k的数。
因此我最好可以每次对[l,r]的查询都可以满足里面的数都是小于等于k的。
那么我们可以先对查询进行排序，按照k从小到大排序。然后对a[i]进行从小到大排序。
然后我们对排序后的查询重新进行处理，由于现在的查询k是从小到大的，那么我们每次查询之前，我们都从a[i]数组中把小于等于k的数字放入树状数组中。然后再去查询。

上述的思路方法就是离线处理。问题就解决了，这样做复杂度是m*logn。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tree[100040],ans[100040];
int lowbit(int x){
    return x&(-x);
}
void update(int x){
    while(x<=n){
        tree[x]+=1;
        x+=lowbit(x);
    }
}
int getans(int x){
    int ans=0;
    while(x){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
pair<int,int>p[100040];
struct node{
    int l,r,k,idx;
}q[100005];
bool cmp(node a,node b){
    return a.k<b.k;
}
bool cmp1(pair<int,int>a,pair<int,int>b){
    return a.first<b.first;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        p[i]=make_pair(x,i);
    }
    sort(p+1,p+1+n,cmp1);
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r>>q[i].k;
        q[i].idx=i;
    }
    sort(q+1,q+1+m,cmp);

    int j=1;
    for(int i=1;i<=m;i++){
        for(;j<=n;j++){
            if(p[j].first<=q[i].k)update(p[j].second);
            else break;
        }
        ans[q[i].idx]=getans(q[i].r)-getans(q[i].l-1);
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}