5 2 1 3 1 5 5 2 5 1 3 3 1 5 2 7 3 9 1 0
3HintIn the sample, three monsters with origin HP 5, 7 and 9 will survive.
题解及代码：
官方的思路挺好：
比赛的时候开始使用线段树来做，结果超时，然后换成树状数组来做，使用树状数组维护区间和，感觉和官方思路还是差上一线啊。
官方：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define maxn 100010
using namespace std;
typedef long long ll;
ll delta[maxn];
int main()
{
int n,m,l,r;
ll v;
while(scanf("%d",&n)&&n)
{
memset(delta,0,sizeof(delta[0])*(n+5));
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%d%d%I64d",&l,&r,&v);
delta[l]+=v;
delta[r+1]-=v;
}
for(int i=2;i<=n;i++)
{
delta[i]+=delta[i-1];
}
for(int i=n-1;i>=1;i--)
{
delta[i]+=delta[i+1];
}
int ans=0;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%I64d%d",&v,&r);
if(v>delta[r])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
个人思路：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=100000+100;
LL n;
LL c1[MAX],c2[MAX];
LL lowbit(LL x)
{
return x&(-x);
}
void Update(LL x,LL d,LL *c)
{
while(x<=n)
{
c[x]+=d;
x+=lowbit(x);
}
}
LL Query(LL x,LL *c)
{
LL sum=0;
while(x>0)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
LL x,y,d,t,h;
int m;
while(scanf("%I64d",&n)&&n)
{
memset(c1,0,sizeof c1);
memset(c2,0,sizeof c2);
scanf("%d",&m);
for(int i=0; i<m; i++)
{
scanf("%I64d%I64d%I64d",&x,&y,&d);
Update(x,d,c1);
Update(y+1,-d,c1);
Update(x,x*d,c2);
Update(y+1,-(y+1)*d,c2);
}
scanf("%d",&m);
int ans=0;
for(int i=0; i<m; i++)
{
scanf("%I64d%I64d",&h,&x);
t=Query(n,c1)*(n+1)-Query(x-1,c1)*x-Query(n,c2)+Query(x-1,c2);
if(h>t) ans++;
}
printf("%d\n",ans);
}
return 0;
}
hdu 4970 Killing Monsters,布布扣,bubuko.com
原文：http://blog.csdn.net/knight_kaka/article/details/38686301