SDUT 3915 从零开始的异世界生活【线段树，区间求和】

题目链接：http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3915.html


线段树水过…（蕾姆好可爱啊 我做这道题就是为了蕾姆 ）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll ans,add[4*N],sum[4*N];
int n,m,x,y,hurt[N];
struct node
{
    int ret,num,deth;
}p[N];
bool cmp(node a,node b)
{return a.deth<=b.deth;}
void build(int i,int l,int r)
{
    if(l==r)
    {
        sum[i]=hurt[l];
        return;
    }
    int mid=l+r>>1;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    sum[i]=sum[2*i]+sum[2*i+1];
}
void Add(int i,int l,int r,int k)
{
    add[i]=add[i]+k;
    sum[i]=sum[i]+(r-l+1)*k;
}
void pushdown(int i,int l,int r,int mid)
{
    if(add[i]==0)return;
    Add(2*i,l,mid,add[i]);
    Add(2*i+1,mid+1,r,add[i]);
    add[i]=0;
}
ll query(int i,int l,int r,int x,int y)
{
    if(l>y||r<x)return 0;
    if(l>=x&&r<=y)return sum[i];
    int mid=l+r>>1;
    pushdown(i,l,r,mid);
    return query(2*i,l,mid,x,y)+query(2*i+1,mid+1,r,x,y);
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            cin>>hurt[i];
        build(1,1,n);
        for(int i=1;i<=m;i++)
            cin>>p[i].deth>>p[i].ret>>p[i].num;
        sort(p+1,p+m+1,cmp);x=1;ans=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=p[i].num;j++)
            {
                y=p[i].deth;
                ans=ans+query(1,1,n,x,y);
                x=p[i].ret;
            }
        }
        ans=ans+query(1,1,n,x,n);
        printf("%lld\n",ans);
    }
    return 0;
}