Sdut 2880 Devour Magic

发表于   |   分类于

Sdut 2880 Devour Magic

链接

Devour Magic

题意

有n个小怪，它们每个单位时间魔力值都会增加1，初始魔力值都为0.现在又来了个大怪兽，可以吸收它们的魔力.
给定m组操作，[t,l,r],即大怪兽会吸收在t时刻吸收[l,r]区间内所有小怪的魔力值(即被吸收后，这些小怪魔力值变为0，继续随时间增长).问大怪兽最终吸收的魔力总和.

分析

如果直接暴力，时间复杂度为O(m*n),很显然会TLE.对于每次操作：
1.需先更新每个怪的魔力值(每单位时间增长1)，即第i次操作时每个怪的魔力值需增加$t_{i}-t_{i-1}$
2.查询本次能吸收的魔力和；3.小怪的魔力被吸收后，其魔力值都变为0，即清零操作。
由于涉及区间的更新及查询，可以应用 线段树+延迟标记 时间复杂度O(mlgn)
注：若区间需清零，那该区间不管之前需增加多少魔力值，都要清成零

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<stdio.h>  
#include<iostream>  
#include<string.h>  
#define N 100010  
using namespace std;  
typedef long long LL;  
struct stu{  
    LL sum;    //魔法总和
    int add;   //延迟标记每个怪需增加的值
    bool reset;  //清零操作
}tree[N<<2];  
int t[N],l[N],r[N];  
void pushUp(int node)  
{  
    tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;  
}  
void pushDown(int node,int l,int r)  
{  
    if(tree[node].reset==true){    //需先清零后更新总和（先reset后add)
        tree[node<<1].sum=tree[node<<1|1].sum=0;  
        tree[node<<1].reset=tree[node<<1|1].reset=true;  
        tree[node].reset=false;  
        tree[node<<1].add=tree[node<<1|1].add=0; //该区间所有值都清零，其延迟要增加的值也清零
    }  
    if(tree[node].add>0){  
        int mid=(l+r)>>1;  
        tree[node<<1].sum+=tree[node].add*(mid-l+1);  
        tree[node<<1|1].sum+=tree[node].add*(r-mid);  
        tree[node<<1].add+=tree[node].add;   //延迟累加
        tree[node<<1|1].add+=tree[node].add;  
        tree[node].add=0;  
    }  
}  
LL query(int l,int r,int node,int ql,int qr)  
{  
    if(ql<=l&&r<=qr){  
        return tree[node].sum;  
    }  
    pushDown(node,l,r);  
    int mid=(l+r)>>1;  
    LL sum=0;  
    if(ql<=mid)  
        sum+=query(l,mid,node<<1,ql,qr);  
    if(mid<qr)  
        sum+=query(mid+1,r,node<<1|1,ql,qr);  
    return sum;  
}  
void update(int l,int r,int node,int ul,int ur,int val)  
{  
    if(ul<=l&&r<=ur){  
        if(val==0){  
            tree[node].sum=0;  
            tree[node].reset=true;  
            tree[node].add=0;  //该区间所有值都清零，其延迟要增加的值也清零
        }  
        else{  //区间[l,r]所有值都增加val,即总和需增加val乘以个数
            tree[node].sum+=(r-l+1)*val;
            tree[node].add+=val;  //会多次延迟，标记累加
        }  
        return ;  
    }  
    pushDown(node,l,r);  
    int mid=(l+r)>>1;  
    if(ul<=mid)  
        update(l,mid,node<<1,ul,ur,val);  
    if(mid<ur)  
        update(mid+1,r,node<<1|1,ul,ur,val);  
    pushUp(node);  
}  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--){  
        int n,m;  
        scanf("%d%d",&n,&m);  
        memset(tree,0,sizeof(tree));  
        for(int i=1;i<=m;i++){  
            scanf("%d%d%d",&t[i],&l[i],&r[i]);  
        }  
        t[0]=0;  
        LL ans=0;  
        for(int i=1;i<=m;i++){  
            if(t[i]>t[i-1])  
                update(1,n,1,1,n,t[i]-t[i-1]);  
            ans+=query(1,n,1,l[i],r[i]);  
            update(1,n,1,l[i],r[i],0);  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}