HDU4970 Killing Monsters

文章目录

1. 1. 题意
2. 2. 分析

原题

题意

塔防游戏模拟，给定数目的攻击塔，给定的范围和给定的攻击，有一些怪，有自己的生命值和出现点，计算到终点有多少怪没有被杀死

分析

区间更新，直接树状数组，其实普通数组模拟也可以的，嘛无所谓了，树状数组也挺好写的，然后把给定范围和攻击处理完之后，直接倒着从终点往前，预处理出来从该点出发到终点的所有被攻击值，然后直接输出。

/*树状数组，区间更新wa1:sum[]没有清空。。。以及h应该用long long*/
树状数组，区间更新
wa1:sum[]没有清空。。。以及h应该用long long
*/
#include <bits/stdc++.h>
#define N 100007
using namespace std;
long long sum[100007],c[100007];
int lowbit(int x){
    return x&(-x);
}
void update(int bit,int a){
    while(bit<=N){
        c[bit]+=a;
        bit+=lowbit(bit);
    }
}
long long getsum(int x){
    long long sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){

    int n,m,l,r,d,k,x;
    long long ans,h;
    while(scanf("%d%d",&n,&m)!=EOF&&n!=0){
        memset(c,0,sizeof(c));
        memset(sum,0,sizeof(sum));
        ans=0;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&l,&r,&d);
            update(l,d);//区间更新为容斥
            update(r+1,-d);
        }
        for(int i=n;i>0;i--){//预处理出每一个点到终点的所有伤害值
            sum[i]=sum[i+1]+getsum(i);
        }
        scanf("%d",&k);
        ans=0;
        for(int i=0;i<k;i++){
            scanf("%I64d%d",&h,&x);
            if(h>sum[x]){
                ans++;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}