题目链接:hdu 3954 Level up
题目大意:N个英雄,M个等级,初始等级为1,给定每个等级需要的经验值,Q次操作,操作分两种,W l r x:表示l~r之间的英雄每个人杀了x个怪物;Q l r:表示询问l~r之间经验值最大的英雄经验值为多少。每轮杀怪,每只怪物的经验和当前等级成正比。
解题思路:线段树维护,每个节点维护最大值,区间内还需要杀多少怪就能升级的最小值,如果这个最小值为0,就要将懒惰标记pushdown到最底层,将英雄升级。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10005;
const int INF = 0x3f3f3f3f;
int N, K, Q, need[15];
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], s[maxn << 2];
int ad[maxn << 2], nd[maxn << 2], rk[maxn << 2];
void maintain(int u, int d);
inline void pushup(int u) {
s[u] = max(s[lson(u)], s[rson(u)]);
rk[u] = max(rk[lson(u)], rk[rson(u)]);
nd[u] = min(nd[lson(u)], nd[rson(u)]);
}
inline void pushdown(int u) {
if (ad[u]) {
maintain(lson(u), ad[u]);
maintain(rson(u), ad[u]);
ad[u] = 0;
}
}
inline void levelup(int u) {
ad[u] = 0;
while (s[u] >= need[rk[u] + 1])
rk[u]++;
int tmp = need[rk[u] + 1] - s[u];
nd[u] = tmp / rk[u] + (tmp % rk[u] ? 1 : 0);
}
void maintain (int u, int d) {
nd[u] -= d;
ad[u] += d;
s[u] += rk[u] * d;
if (nd[u] <= 0) {
if (lc[u] == rc[u])
levelup(u);
else {
pushdown(u);
pushup(u);
}
}
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
s[u] = ad[u] = nd[u] = rk[u] = 0;
if (l == r) {
rk[u] = 1;
nd[u] = need[2];
return;
}
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify (int u, int l, int r, int d) {
if (l <= lc[u] && rc[u] <= r) {
maintain(u, d);
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
modify(lson(u), l, r, d);
if (r > mid)
modify(rson(u), l, r, d);
pushup(u);
}
int query (int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r)
return s[u];
pushdown(u);
int mid = (lc[u] + rc[u]) / 2, ret = 0;
if (l <= mid)
ret = max(ret, query(lson(u), l, r));
if (r > mid)
ret = max(ret, query(rson(u), l, r));
pushup(u);
return ret;
}
void init () {
scanf("%d%d%d", &N, &K, &Q);
for (int i = 2; i <= K; i++)
scanf("%d", &need[i]);
need[K+1] = INF;
build(1, 1, N);
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
init();
printf("Case %d:\n", kcas);
char op[5];
int t, l, r;
while (Q--) {
scanf("%s%d%d", op, &l, &r);
if (op[0] == 'W') {
scanf("%d", &t);
modify(1, l, r, t);
} else
printf("%d\n", query(1, l, r));
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241