换个角度思考

题意：给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数

思路：将所有询问按x升序排列，a序列也按升序排列，然后每次询问当前[l,r,x]之前把ai小于等于x的ai在树状数组中加入他对应的原下标（只需要对应原下标位置+1就行)，然后询问[l,r]区间有多少个数。

代码：

#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;

typedef long long ll;

int shu[500005];
int n, m;
struct w
{
    int l, r, x, s;
}w[100005];

struct a
{
    int a, s;
}a[100005];

bool cmp(struct w a, struct w b)
{
    return a.x<b.x;
}

bool cmp1(struct a x,struct a y)
{
    return x.a<y.a;
}

bool cmp2(struct w a, struct w b)
{
    return a.s<b.s;
}

void add(int x,int y)
{
    while(x<=n)
    {
        shu[x]++;
        int k=x&(-x);
        x=x+k;
    }
}

int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s+=shu[x];
        int k=x&(-x);
        x=x-k;
    }
    return s;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i].a);
        a[i].s=i+1;
    }
    sort(a,a+n,cmp1);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&w[i].l,&w[i].r,&w[i].x);
        w[i].s=i;
    }
    sort(w,w+m,cmp);
    for(int i=0, j=0;j<m;)
    {
        while(i<n&&a[i].a<=w[j].x)
        {
            add(a[i].s,1);
            i++;
        }
        int p=sum(w[j].r)-sum(w[j].l-1);
        w[j].l=p;
        j++;
    }
    sort(w,w+m,cmp2);
    for(int i=0;i<m;i++)
    {
        printf("%d\n",w[i].l);
    }
    return 0;
}