hdu 3956 Level up

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意不要读错

在一次攻击中,变化并不是动态的,即当前等级为k,经验为e

那么本次攻击的经验就是e*k,虽然可能早就超过了这个等级的限制,超出了很多个等级,但是并不会因为超出了就一直动态的变化(否则是会出现实数的)

但是在这次攻击结束后,等级是发生了变化

因为只有10个等级,对已一个线段树的节点,用10个变量来记录一些信息

就是该区间内,等级为k的最大经验值

对一个区间修改后,看看是否有哪个等级会发生升级,是的话,就从这个节点深入下去,一直到叶子,把能更新的一次性更新干净

LevelUp,PushDown,PushUp,都是一些细节重点

这题挺好,想清楚了,助于理解线段树

关于线段树信息的维护,PushDown,PushUp的意义有了更深的理解

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 10010
#define M 15
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,K,q,need[M];
struct SegTree{
int l,r,mid;
int Max[M];
int lazy;
SegTree(){}
SegTree(int __l,int __r){
l = __l ; r = __r; mid = (l+r)>>1;
cl(Max,-1); lazy = 0;
}
}t[N<<2];

void PushUp(int rt){
for(int i = K; i >= 1; i--){
t[rt].Max[i] = max(t[lson(rt)].Max[i] , t[rson(rt)].Max[i]);
}
}

void PushDown(int rt){
if(t[rt].lazy == 0) return ;
t[lson(rt)].lazy += t[rt].lazy;
t[rson(rt)].lazy += t[rt].lazy;
for(int i = 1; i <= K; i++){
if(t[lson(rt)].Max[i] != -1) t[lson(rt)].Max[i] += i * t[rt].lazy;
if(t[rson(rt)].Max[i] != -1) t[rson(rt)].Max[i] += i * t[rt].lazy;
}
t[rt].lazy = 0;
}

void LevelUp(int rt,int k){
if(t[rt].l == t[rt].r){
while(k < K){
if(t[rt].Max[k] < need[k+1]) break;
t[rt].Max[k+1] = t[rt].Max[k];
t[rt].Max[k] = -1;
k++;
}
return ;
}
PushDown(rt);
if(t[lson(rt)].Max[k] >= need[k]) LevelUp(lson(rt),k);
if(t[rson(rt)].Max[k] >= need[k]) LevelUp(rson(rt),k);
PushUp(rt);
}

void build(int rt,int a ,int b){
t[rt] = SegTree(a,b);
if(a == b){
t[rt].Max[1] = 0; return ;
}
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
PushUp(rt);
}

void updata(int rt,int a,int b,int val){
if(t[rt].l == a && t[rt].r == b){
t[rt].lazy += val;
for(int i = K; i >= 1; i--){
if(t[rt].Max[i] == -1) continue;
t[rt].Max[i] += val*i;
if(i < K && t[rt].Max[i] >= need[i+1])
LevelUp(rt,i);
}
return ;
}
PushDown(rt);
int mid = t[rt].mid;
if(b <= mid)
updata(lson(rt),a,b,val);
else if(a > mid)
updata(rson(rt),a,b,val);
else{
updata(lson(rt),a,mid,val);
updata(rson(rt),mid+1,b,val);
}
PushUp(rt);
}

int query(int rt,int a,int b){
if(t[rt].l == a && t[rt].r == b){
for(int i = K; i >= 1; i--){
if(t[rt].Max[i] != -1)
return t[rt].Max[i];
}
}
PushDown(rt);
int mid = t[rt].mid;
if(b <= mid)
return query(lson(rt),a,b);
else if(a > mid)
return query(rson(rt),a,b);
else{
int L = query(lson(rt),a,mid);
int R = query(rson(rt),mid+1,b);
return max(L,R);
}
}

int main(){
int T;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
printf("Case %d:\n",cas);
scanf("%d%d%d",&n,&K,&q);
cl(need,0);
for(int i = 2; i <= K; i++)
scanf("%d",&need[i]);
build(1,1,n);
while(q--){
char op[5]; int a,b,val;
scanf("%s",op);
if(op[0] == 'W'){
scanf("%d%d%d",&a,&b,&val);
updata(1,a,b,val);
}
else{
scanf("%d%d",&a,&b);
int res = query(1,a,b);
printf("%d\n",res);
}
}
puts("");
}
return 0;
}