题意
数轴上有n个点，有m座炮塔，每个炮塔有一个攻击范围和伤害，有k个怪物，给出他们的初始位置和血量，问最后有多少怪物能活着到达n点。n<=100000
分析
对于某个怪物，什么情况下它可以活着到达N点？
对于每个怪物，求他出现的位置到结尾的这段区间的炮塔的伤害总和，如果它的血量大于这个和，那么它就可以活着到达N点。
也就是说，先更新m个区间的值，然后对于每个怪物求一个后缀和。
想到了什么？线段树？树状数组？不存在的。差分就可以解决这个题。因为这个题区间更新和查询时分开的，所以不需要动态的进行修改。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 const int maxn=100000+100; 8 int n,m,k,ans; 9 int cha[maxn],a[maxn]; 10 long long sum[maxn]; 11 int main(){ 12 while(scanf("%d",&n)!=EOF&&n){ 13 memset(cha,0,sizeof(cha)); 14 scanf("%d",&m); 15 int l,r,v; 16 for(int i=1;i<=m;i++){ 17 scanf("%d%d%d",&l,&r,&v); 18 cha[l]+=v;cha[r+1]-=v; 19 } 20 sum[0]=0; 21 for(int i=1;i<=n;i++){ 22 sum[i]=sum[i-1]+cha[i]; 23 a[i]=sum[i]; 24 } 25 sum[0]=0; 26 for(int i=1;i<=n;i++){ 27 sum[i]=sum[i-1]+a[i]; 28 } 29 ans=0; 30 scanf("%d",&k); 31 long long a; 32 int b; 33 for(int i=1;i<=k;i++){ 34 scanf("%lld%d",&a,&b); 35 if(sum[n]-sum[b-1]<a) 36 ans++; 37 } 38 printf("%d ",ans); 39 } 40 return 0; 41 }