题意是给你一个序列   m次询问    每次询问区间内比给定值小的有多少个     

首先相到的肯定是线段树   但是按常规的做不容易做出来    这里用到离线处理   及先把所有的询问区间输入存起来并保存原来id      进行如下处理

对每段区间按高度从小到大排序  把序列也按从小到大排序并保存原来id   

i表示插入位置  j表示询问位置   如果当前i表示的高度比当前j表示的高度小则跟新  否则查询（这样子的原因是当查询当前j表示的高度时只用跟上比他小的高度  ）具体见代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)

struct node
{
    int high;
    int ii;
}A[100100];
struct Node
{
    int L,R,h,i;
}f[100100];
int cmp1(node a,node b)
{
    return a.high<b.high;
}
int cmp2(Node a,Node b)
{
    return a.h<b.h;
}
int num[4*100000];
int update(int L,int R,int pos,int mark)
{
    num[mark]+=1;
    if(L==R&&L==pos)
    {
        return 0;
    }    
    int mid=(L+R)/2;
    if(pos<=mid)
    {
        update(L,mid,pos,LL(mark));
    }
    else update(mid+1,R,pos,RR(mark));
    return 0;
}
int find(int L,int R,int left,int right,int mark)
{
    if(L==left&&R==right)
    {
        return num[mark];
    }    
    int mid=(L+R)/2;
    if(right<=mid)
    {
        return find(L,mid,left,right,LL(mark));
    }
    else if(left>mid)
    {
        return find(mid+1,R,left,right,RR(mark));
    }
    else return find(L,mid,left,mid,LL(mark))+find(mid+1,R,mid+1,right,RR(mark));
}
int main()
{
    int n,m,i,j,a,T,b,c,d=1;
    int print[100010];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&A[i].high);
            A[i].ii=i;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&f[i].L,&f[i].R,&f[i].h);
            f[i].L++;
            f[i].R++;
            f[i].i=i;
        }
        sort(A+1,A+1+n,cmp1);
        sort(f+1,f+1+m,cmp2);
        memset(num,0,sizeof(num));
        int j=1;
        for(i=1;i<=n;)
        {
            if(A[i].high>f[j].h)
            {
                print[f[j].i]=find(1,n,f[j].L,f[j].R,1);
                j++;
                if(j>m) break;
            }
            if(A[i].high<=f[j].h)
            {
                update(1,n,A[i].ii,1);
                i++;
            }
        }
        while(j<=m)
        {
            print[f[j].i]=find(1,n,f[j].L,f[j].R,1);
            j++;
        }
        printf("Case %d:\n",d++);
        for(i=1;i<=m;i++)
        printf("%d\n",print[i]);
    }
    return 0;
}

hdu4417 线段树+离线处理