首页 > 代码库 > hdu 4970 树状数组 “改段求段”
hdu 4970 树状数组 “改段求段”
题意:塔防。给1--n,给出m个塔,每个塔有攻击力,给出k个怪兽的位子和血量,问有几只可以到达n点。
今天刚刚复习了树状数组,就碰到这个题,区间更新、区间求和类型。第三类树状数组可以斩。
注意一下大数即可。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; __int64 tree1[100010],tree2[100010]; int n,m; void add_b(int x,int c) { while(x>0) { tree1[x]+=c; x-=(x&(-x)); } } __int64 sum_b(int x) { // if(x==0)return 0; __int64 res=0; while(x<=n) { res+=tree1[x]; x+=(x&(-x)); } return res; } void add_c(int x,int c) { if(x<1)return ; int tx=x; while(x<=n) { tree2[x]+=c*tx; x+=(x&(-x)); } } __int64 sum_c(int x) { __int64 res=0; while(x>0) { res+=tree2[x]; x-=(x&(-x)); } return res; } __int64 inline sum(int x) { if(x>=1) return sum_b(x)*x+sum_c(x-1); else return 0; } int main() { while(~scanf("%d",&n)&&n) { scanf("%d",&m); memset(tree1,0,sizeof(tree1)); memset(tree2,0,sizeof(tree2)); int l,r,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&l,&r,&c); add_b(r,c);add_b(l-1,-c); add_c(r,c); add_c(l-1,-c); } int k; scanf("%d",&k); int counted=0; __int64 xi,hi; for(int i=1;i<=k;i++) { scanf("%I64d%I64d",&hi,&xi); if(hi>sum(n)-sum(xi-1)){counted++;} } printf("%d\n",counted); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。