链接：

@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

在这里插入图片描述

输入描述:

第一行两个整数n,m 第二行n个整数表示序列a的元素，序列下标从1开始标号，保证1 ≤ ai ≤ 10^5^
之后有m行，每行三个整数(l,r,k)，保证1 ≤ l ≤ r ≤ n，且1 ≤ k ≤ 10^5^

输出描述:

对于每一个询问，输出一个整数表示答案后回车

示例1
输入

5 1
1 2 3 4 5
1 5 3

输出

3

备注:
数据范围
1 ≤ n ≤ 10^5^
1 ≤ m ≤ 10^5^

题解：

主席树，树状数组等都可以做

主席树做法：

简单提一句主席树
主席树的本体其实是线段树，也就是很多棵线段树，用以存一段数字区间出现次数，主席树经常用于求一个序列内的第 k 小
在这里，主席树就是提前预处理好每个点的权值线段树，查询时，可以直接用r时刻前缀小于x的数量减去l-1的数量，剩下的就是[l,r]区间值
也就是[L,R]=[1,R]-[1,L-1]，查询后两者相减即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+2;
int n,m;
int a[maxn];
vector<int>edge[maxn*4];

void build(int id,int l,int r)
{
    edge[id].clear();

    for(int i=l;i<=r;i++) edge[id].push_back(a[i]);

    sort(edge[id].begin(),edge[id].end());

    if(l==r) return;
    int mid=(l+r)>>1;

    build(id<<1,l,mid);

    build(id<<1|1,mid+1,r);
}//建树 
int query(int id,int L,int R,int l,int r,int k)
{  
     int sum=0;
    vector<int>::iterator it;
    if(l<=L&&R<=r)
    {
        it=upper_bound(edge[id].begin(),edge[id].end(),k);//二分查找，第一个大于k的数，返回地址 
        return it-edge[id].begin();//两者做差的个数
    }

    int mid=(L+R)/2;

    if(l<=mid)
    {
         sum+=query(id*2,L,mid,l,r,k);
    }
    if(mid<r)
    {
        sum+=query(id*2,mid+1,R,l,r,k);
     } 
    return sum;
}
int main()
{ 
    int l,r,k;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) cin>>a[i];

    build(1,1,n);

    while(m--)
    {
       cin>>l>>r>>k;
        printf("%d\n",query(1,1,n,l,r,k));
    }
    return 0;
}

代码：

树状数组：

首先需要离线操作，我们每次查询都是要知道左右区间以及x，相当于同时有两个东西未知需要操作。通过离散后，我们可以控制其中一部分，另外一部分未知变化，例如：第一种我们查询[l,r]内有多少数满足条件，我们就要保证所有数都小于x；第二种如何问有多少数小于等于x，就保证范围取定于[l,r]。这样更高效，当然占空间更多。

简单的说：
离线操作：读入所有的操作数据，然后一次性处理。
在线操作：每读入一个操作数据，就进行一次操作。

第一种：
我们在保证所有数都是小于等于x的情况下来查询[l,r]有多少个数
每次询问[l,r,x]之前，把小于等于x的ai都加入加入到一个另外的位置上，这样里面存放的都是满足条件的数，直接询问即可

第二种：
保证所有数都在[l,r]区间的情况下，查询小于等于x的数量
我们可以在离线时，将[l,r]区间问题转化成 [ 1 , l-1 ] , [ 1 , r ] 两个区间，这样就可以用树状数组来解决

（这是邓老师的讲解，我加入自己的理解写出来的）

代码写完再更

更扯淡的方法！！！

这题貌似优化暴力就能过。。。
就是直接模拟，不知为啥过了。。快读都还没用上
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

const int N = 1e5 + 3;
int a[N];

int main() {
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <= n; ++i)   cin>>a[i]; 
    while (m--) {

        int l,r,k;
        cin>>l>>r>>k;

        int sum = 0;
        for (int i = l; i <= r; ++i)
            if (a[i] <= k)    ++sum;
        printf("%d\n", sum);
    }
    return 0;
}