解题思路:这道题要求某区间内比h小的个数,其实这里可以类似于树状数组求逆序数那样。关键是如何转换成树状数组的模型,这才是本题的难点。
我们首先分析,如果知道h在该区间的哪个位置,那么剩下的就很好做了。我们还可以发现,如果找到了当前的比h小的所有点(大于的点我们先忽略掉),那么我们就可以用树状数组求它的[l,r]区间的和。这样就跟树状数组有了一点联系,但是还不够,因为我们发现,h的大小会影响我们所要找的区间。什么意思呢?就是我们先找到的是h1,再找h2,但h1>h2,就会出现这样的问题:h1所对应的区间找到了,但再找h2时,它对应的区间中可能会有比h2大的数,这样就不符合条件了。所以说这里有一个离线算法,就是先把所有的询问存下来,再按照h的大小进行从小到大排序,然后根据h的大小,从小到大地一个个插入所有区间内的数,这样就符合条件了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
struct Query
{
int l,r,h;
int id;
bool operator < (Query a)
{
return h < a.h;
}
}q[maxn];
struct Node
{
int num;
int id;
bool operator < (Node a)
{
return num < a.num;
}
}a[maxn];
int n,m;
int tree[maxn<<2],ans[maxn];
int lowbit(int x)
{
return x & (-x);
}
void update(int x,int d)
{
for(int i = x; i <= n; i += lowbit(i))
tree[i] += d;
}
int getsum(int x)
{
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
sum += tree[i];
return sum;
}
int main()
{
int t,cas = 1;
cin >> t;
while(t--)
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i].num;
a[i].id = i;
}
for(int i = 1; i <= m; i++)
{
cin >> q[i].l >> q[i].r >> q[i].h;
q[i].l++, q[i].r++;
q[i].id = i;
}
sort(a+1,a+1+n);
sort(q+1,q+1+m);
memset(tree,0,sizeof(tree));
int idx = 1;
for(int i = 1; i <= m; i++)
{
while(q[i].h >= a[idx].num && idx <= n)
{
update(a[idx].id,1);
idx++;
}
ans[q[i].id] = getsum(q[i].r) - getsum(q[i].l-1);
}
printf("Case %d:\n",cas++);
for(int i = 1; i <= m; i++)
printf("%d\n",ans[i]);
}
return 0;
}