題意:塔防。給1--n,給出m個塔,每個塔有攻擊力,給出k個怪獸的位子和血量,問有幾只可以到達n點。
今天剛剛復習了樹狀數組,就碰到這個題,區間更新、區間求和類型。第三類樹狀數組可以斬。
注意一下大數即可。
#include#include #include 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 sum(n)-sum(xi-1)){counted++;} } printf("%d\n",counted); } return 0; }