题目地址：HDU 4970
先进行预处理。在每一个炮塔的火力范围边界标记一个点。
然后对每一个点的伤害值扫一遍就能算出来。
然后在算出每一个点到终点的总伤害值，并保存下来，也是扫一遍就可以。
最后在询问的时候直接推断就可以，复杂度O(2*n).
代码例如以下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 110000
#define LL __int64
#define lmin 1
#define rmax n
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define now l,r,rt
#define int_now LL l,LL r,LL rt
LL c[maxn] , sum[maxn] ;
int main()
{
LL n , m , l , r , x , i , temp , num ;
while(scanf("%I64d", &n) && n)
{
num = 0 ;
memset(c,0,sizeof(c));
scanf("%I64dd", &m);
while(m--)
{
scanf("%I64d %I64d %I64d", &l, &r, &x);
c[l] += x ;
c[r+1] -= x ;
}
sum[0] = 0 ;
for(i = 1 ; i <= n ; i++)
{
sum[i] = sum[i-1] + c[i] ;
}
for(i = n-1 ; i >= 1 ; i--)
{
sum[i] = sum[i] + sum[i+1] ;
}
scanf("%I64d", &m);
while(m--)
{
scanf("%I64d %I64d", &x, &l);
if( sum[l] < x )
num++ ;
}
printf("%I64d\n", num);
}
return 0;
}