HDU 4417 Super Mario [树状数组+离线操作]【数据结构】
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4417 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Input Output Sample Input Sample Output Source 解题思路: 如果题目中没有要求
很明显,直接在线的话并不能在良好复杂度内解决问题(后来发现是有的只不过我不会。。),离线的话考虑还是很容易的。 首先题目既然要求比h小的,那么我们可以对
这种查询区间的操作用[树状数组/线段树]都能很好完成,树状数组的话实现相对容易,所以我采用了树状数组. 最后的最后!!!! 附本题代码 #include <bits/stdc++.h>
using namespace std;
const int N = 100000+7;
/***********************************************************************/
struct node1{
int a,id;
}aa[N];
struct node2{
int l,r,h,id;
}bb[N];
bool cmp1(node1 A,node1 B){
return A.a<B.a;
}
bool cmp2(node2 A,node2 B){
return A.h<B.h;
}
#define lowbit(x) (x&-x)
int tree[N];
void update(int ind,int val){
for(int i=ind;i<=N;i+=lowbit(i))
tree[i]+=val;
}
int getSum(int ind){
int ans = 0;
for(int i=ind;i;i-=lowbit(i)) ans+=tree[i];
return ans;
}
int ans[N];
int main(){
int _,kcase=0;
scanf("%d",&_);
while(_--){
memset(tree,0,sizeof(tree));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&aa[i].a);
aa[i].id=i;
}
int l,h;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&h);
bb[i].l=l+1,bb[i].r=r+1,bb[i].h=h,bb[i].id=i;
}
sort(aa+1,aa+n+1,cmp1);
sort(bb+1,bb+m+1,cmp2);
for(int i=1,j=1;i<=m;i++){
while(j<=n&&bb[i].h>=aa[j].a) update(aa[j++].id,1);
ans[bb[i].id]=getSum(bb[i].r)-getSum(bb[i].l-1);
}
printf("Case %d:n",++kcase);
for(int i=1;i<=m;i++) printf("%dn",ans[i]);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |