【HDU4970】Killing Monsters

题意

数轴上有n个点，有m座炮塔，每个炮塔有一个攻击范围和伤害，有k个怪物，给出他们的初始位置和血量，问最后有多少怪物能活着到达n点。n<=100000

分析

对于某个怪物，什么情况下它可以活着到达N点？

对于每个怪物，求他出现的位置到结尾的这段区间的炮塔的伤害总和，如果它的血量大于这个和，那么它就可以活着到达N点。

也就是说，先更新m个区间的值，然后对于每个怪物求一个后缀和。

想到了什么？线段树？树状数组？不存在的。差分就可以解决这个题。因为这个题区间更新和查询时分开的，所以不需要动态的进行修改。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn=+;

 int n,m,k,ans;

 int cha[maxn],a[maxn];

 long long sum[maxn];

 int main(){

     while(scanf("%d",&n)!=EOF&&n){

         memset(cha,,sizeof(cha));

         scanf("%d",&m);

         int l,r,v;

         for(int i=;i<=m;i++){

             scanf("%d%d%d",&l,&r,&v);

             cha[l]+=v;cha[r+]-=v;

         }

         sum[]=;

         for(int i=;i<=n;i++){

             sum[i]=sum[i-]+cha[i];

             a[i]=sum[i];

         }

         sum[]=;

         for(int i=;i<=n;i++){

             sum[i]=sum[i-]+a[i];

         }

         ans=;

         scanf("%d",&k);

         long long a;

         int b;

         for(int i=;i<=k;i++){

             scanf("%lld%d",&a,&b);

             if(sum[n]-sum[b-]<a)

                 ans++;

         }

         printf("%d\n",ans);

     }

 return ;

 }