Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)
1 10 10 0 5 2 7 5 4 3 8 7 7 2 8 6 3 5 0 1 3 1 1 9 4 0 1 0 3 5 5 5 5 1 4 6 3 1 5 7 5 7 3
Case 1: 4 0 0 3 1 2 0 1 5 1
题解：
因为是线段树专题的最后几题了。。还以为很难没看题就搜了博客，知道题意后发现用离线操作这题根本不难。。
题意：
给你n个序列，m个询问，每个询问有区间[x,y]，和后面的数组h，问你区间内不大于h的数字和是多少
思路：
显然是个离线操作题，先将子序列存起来，按照子序列的高度从小到大排序，再把询问存起来，把询问按照高度从小到大排序，然后建树，赋初值为0，然后就遍历询问，每次看当前更新的子序列高度是否大于了询问高度，如果是就处理询问，就是个简单的区间求和了，如果不是就更新子序列的位置，直到子序列更新到底或者已经大于了询问高度线段树和树状数组都可以做吧，我先用线段树写一遍，作为练习
ps：
刚刚完成的树状数组版的代码：附上链接点击打开链接，速度比线段树快了一倍多，内存也小多了
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<deque>
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
struct node
{int l,r;int num;//存区间内已经更新了几个数
}t[100005*4];
void Build(int l,int r,int k)//日常建树
{t[k].l=l;t[k].r=r;t[k].num=0;if(l==r)return;int mid=M;Build(l,mid,lson);Build(mid+1,r,rson);
}
void update(int pos,int k)//日常更新
{if(t[k].l==t[k].r){t[k].num=1;return;}int mid=M;if(pos<=mid)update(pos,lson);elseupdate(pos,rson);t[k].num=t[lson].num+t[rson].num;
}
int query(int l,int r,int k)//日常询问
{if(t[k].l==l&&t[k].r==r){return t[k].num;}int mid=M;int p;if(r<=mid)return query(l,r,lson);else if(l>mid)return query(l,r,rson);elsereturn query(l,mid,lson)+query(mid+1,r,rson);
}
struct qu
{int id;//存询问的idint h;//询问高度int l,r;
}q[100005];
struct sub
{int pos;//子序列初始位置int h;//子序列高度
}s[100005];
int cmp1(qu x,qu y)//比较函数，用于询问按高度从小到大排序
{return x.h<y.h;
}
int cmp2(sub x,sub y)//比较函数，用于子序列按高度从小到大排序
{return x.h<y.h;
}
int answer[100005];/存答案
int main()
{int i,j,k,n,m,test,o,tot;scanf("%d",&test);for(o=1;o<=test;o++){scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&s[i].h);s[i].pos=i;}for(i=0;i<m;i++){scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);q[i].id=i;}sort(s,s+n,cmp2);sort(q,q+m,cmp1);//排序tot=0;Build(0,n-1,1);for(i=0;i<m;i++){while(tot<n&&q[i].h>=s[tot].h)//更新到子序列高度大于当前询问高度为止{update(s[tot].pos,1);tot++;}answer[q[i].id]=query(q[i].l,q[i].r,1);//询问}printf("Case %d:\n",o);for(i=0;i<m;i++)printf("%d\n",answer[i]);}return 0;
}