图片说明

不离线直接查询的麻烦在于查询的时候有两个东西都是未知的——区间左右端点和x。
我们考虑离线，是要通过离线相关的操作把这询问有关的两个不同性质变得只问一个，
也即，如果我们要问区间[l,r]有多少个数就保证当前所有数都是小于等于x的，
如果要问小于等于x有多少个数，就要保证目前只有区间[l,r]里面的东西。
图片说明 

1.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL s[1000005], n=1e5+10;
void add(LL x,LL z) {for (LL i=x;i<=n;i+=(i&(-i))) s[i]+=z;}
LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i-=(i&(-i))) ans+=s[i];return ans;}
LL ask(LL x, LL y){return ask(y)-ask(x-1);}

const int maxn=100050;
struct node{
    int L, R, x, k;
}q[maxn];

struct A{
    int x, i;
}a[maxn];
int ans[maxn];

int main(){

    int n, m; scanf("%d%d", &n, &m);
    int Len=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].x); a[i].i=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].L,&q[i].R, &q[i].x);
        q[i].k=i;
    }
    sort(a+1, a+1+n, [](A &a, A &b){return a.x<b.x;});
    sort(q+1, q+1+m, [](node &a, node &b){return a.x<b.x;});
    int pos=1;
    for(int i=1; i<=m; i++){
        while(pos<=n&&a[pos].x<=q[i].x){
            add(a[pos].i, 1);
            pos++;
        }
        ans[q[i].k]=ask(q[i].L, q[i].R);
    }

    for(int i=1;i<=m;i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}
2.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL s[1000005], n=1e5+10;
void add(LL x,LL z) {for (LL i=x;i<=n;i+=(i&(-i))) s[i]+=z;}
LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i-=(i&(-i))) ans+=s[i];return ans;}
LL ask(LL x, LL y){return ask(y)-ask(x-1);}

const int maxn=100050;
struct node{
    int L, R, x, k;
}q[maxn];

int a[maxn], pos[maxn], ans[maxn];
bool cmp(node a, node b){
    return pos[a.L]==pos[b.L]?(pos[a.L]&1)?a.R<b.R:a.R>b.R:pos[a.L]<pos[b.L];
}

int main(){

    int n, m; scanf("%d%d", &n, &m);
    int Len=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]); pos[i]=i/Len;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].L,&q[i].R, &q[i].x);
        q[i].k=i;
    }
    sort(q+1, q+1+m, cmp);

    int L=1, R=0;
    for(int i=1;i<=m;i++){
        while(L<q[i].L){
            add(a[L], -1);
            L++;
        }
        while(L>q[i].L){
            L--;
            add(a[L], 1);
        }
        while(R<q[i].R){
            R++;
            add(a[R], 1);
        }
        while(R>q[i].R){
            add(a[R], -1);
            R--;
        }
        ans[q[i].k]=ask(1, q[i].x);
    }
    for(int i=1;i<=m;i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}
3.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL s[1000005], n=1e5+10;
void add(LL x,LL z) {for (LL i=x;i<=n;i+=(i&(-i))) s[i]+=z;}
LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i-=(i&(-i))) ans+=s[i];return ans;}
LL ask(LL x, LL y){return ask(y)-ask(x-1);}

const int maxn=200050;
struct node{
    int L, x, y, k;
}q[maxn];

int a[maxn], ans[maxn];

int main(){

    int n, m, tot=0; scanf("%d%d", &n, &m);
    int Len=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        int L, R, x;
        scanf("%d%d%d",&L,&R,&x);
        q[++tot].L=L; q[tot].x=x, q[tot].y=-1, q[tot].k=i;
        q[++tot].L=R; q[tot].x=x, q[tot].y=1, q[tot].k=i;
    }
    sort(q+1, q+1+tot, [](node &a, node &b){return a.L<b.L;});
    int pos=1;
    for(int i=1; i<=n; i++){
        add(a[i], 1);
        while(pos<=tot&&q[pos].L==i){
            ans[q[pos].k]+=q[pos].y*ask(1, q[pos].x);
            if(a[i]<=q[pos].x&&q[pos].y==-1){//因为L是查询L-1消除a[i]的影响
                ans[q[pos].k]++;
            }
            pos++;
        }
    }

    for(int i=1;i<=m;i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}