hdu 4417 离线树状数组

题目大意：
      给你一个数列，然后有m次查询，每次查询一段区间 [l,r] 内不大于 h 的值的个数。
解法：

      离线 树状数组

      预处理 先将数列与查询分别存储在结构体p,q中，并且将其按照h排序，由小到大。

      2、若 p[i].h <= q[j].h，则它会且仅会对从 j 以后的每个 q[j].h 产生影响。于是我们需要在区间中对这个位置加1，然后让 i 向后移动。

#include <cstdio>
#include <algorithm>
using namespace std;
struct Point {
  int l,r,id,x;
}p[100010],q[100010];
int C[100010];
int n,m;
int ans[100010];
int cmp(Point a,Point b){
  return a.x<b.x;
}
int lowbit(int x){
  return x&(-x);
}
int sum(int x){
  int ret=0;
  while (x>0) {
    ret+=C[x];x-=lowbit(x);
  }
  return ret;
}
int add(int x,int d){
  while (x<=n){
    C[x]+=d;x+=lowbit(x);
  }
  return 0;
}
int query(int L,int R){
  return sum(R)-sum(L-1);
}
int main (){
  int T,t=1;
  scanf("%d",&T);
  while (t<=T){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
      scanf("%d",&p[i].x);
      p[i].id=i;
      C[i]=0;
    }
    for (int i=1;i<=m;i++){
      scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
      q[i].id=i;
      q[i].l++;
      q[i].r++;
    }
    sort(p,p+n+1,cmp);
    sort(q,q+m+1,cmp);
    int i,j;
    for (i=j=1;j<=m;j++){
      while (i<=n&&p[i].x<=q[j].x){
        add(p[i].id,1);
        i++;
      }
      //printf("%d %d %d %d %dn",i,q[j].x,q[j].id,q[j].l,q[j].r);
      //for (int k=1;k<=n;k++)
      //  printf("%d ",C[k]);
      //printf("n");
      ans[q[j].id]=query(q[j].l,q[j].r);
    }
    printf("Case %d:n",t);
    for (int j=1;j<=m;j++)
      printf("%dn",ans[j]);
    t++;
  }
  return 0;
}

最后

以上就是温婉电灯胆为你收集整理的hdu 4417 离线树状数组的全部内容，希望文章能够帮你解决hdu 4417 离线树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。