HDU 3954 Level up

题目链接

题意：k个等级，n个英雄，每一个等级升级有一定经验，每次两种操作，一个区间加上val，这样区间内英雄都获得当前等级*val的经验，还有一个操作询问区间经验最大值

思路：由于等级少，所以每一个结点用Max[10]记录下每一个等级的最大值，假设有一个升级就一直找究竟，由于一个英雄升级最多10次，所以这个操作最多就10W次能够接受，剩下就是普通的区间改动区间查询的延迟操作了

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 10005;

const int M = 11;

int t, n, k, qw, need[M];

#define lson(x) ((x<<1)+1)

#define rson(x) ((x<<1)+2)

struct Node {

	int l, r, Max[M], add;

	bool cover;

} node[N * 4];

void build(int l, int r, int x = 0) {

	node[x].l = l; node[x].r = r;

	memset(node[x].Max, -1, sizeof(node[x].Max));

	node[x].Max[1] = 0;

	node[x].add = 0;

	node[x].cover = false;

	if (l == r) return;

	int mid = (l + r) / 2;

	build(l, mid, lson(x));

	build(mid + 1, r, rson(x));

}

bool judge(int x, int v) {

	for (int i = 1; i < k; i++) {

		if (node[x].Max[i] == -1) continue;

		if (node[x].Max[i] + i * v >= need[i + 1]) return true;

	}

	return false;

}

void pushup(int x) {

	node[x].cover = (node[lson(x)].cover && node[rson(x)].cover);

	for (int i = 1; i <= k; i++)

		node[x].Max[i] = max(node[lson(x)].Max[i], node[rson(x)].Max[i]);

}

void pushdown(int x) {

	if (node[x].add) {

		node[lson(x)].add += node[x].add;

		node[rson(x)].add += node[x].add;

		for (int i = 1; i <= k; i++) {

			if (node[lson(x)].Max[i] != -1)

				node[lson(x)].Max[i] += node[x].add * i;

			if (node[rson(x)].Max[i] != -1)

				node[rson(x)].Max[i] += node[x].add * i;

		}

		node[x].add = 0;

	}

}

void add(int l, int r, int v, int x = 0) {

	if (node[x].l >= l && node[x].r <= r && (node[x].cover || !judge(x, v))) {

		node[x].add += v;

		for (int i = 1; i <= k; i++) {

			if (node[x].Max[i] == -1) continue;

			node[x].Max[i] += i * v;

		}

		return;

	}

	if (node[x].l == node[x].r) {

		int have;

		for (int i = 1; i < k; i++) {

			if (node[x].Max[i] != -1) {

				have = node[x].Max[i] + i * v;

				break;

			}

		}

		memset(node[x].Max, -1, sizeof(node[x].Max));

		for (int i = 2; i <= k; i++) {

			if (have < need[i]) {

				node[x].Max[i - 1] = have;

				return;

			}

		}

		node[x].Max[k] = have;

		node[x].cover = true;

		return;

	}

	int mid = (node[x].l + node[x].r) / 2;

	pushdown(x);

	if (l <= mid) add(l, r, v, lson(x));

	if (r > mid) add(l, r, v, rson(x));

	pushup(x);

}

int query(int l, int r, int x = 0) {

	if (node[x].l >= l && node[x].r <= r) {

		for (int i = k; i >= 1; i--) {

			if (node[x].Max[i] == -1) continue;

			return node[x].Max[i];

		}

	}

	int mid = (node[x].l + node[x].r) / 2;

	int ans = 0;

	pushdown(x);

	if (l <= mid) ans = max(ans, query(l, r, lson(x)));

	if (r > mid) ans = max(ans, query(l, r, rson(x)));

	pushup(x);

	return ans;

}

int main() {

	int cas = 0;

	scanf("%d", &t);

	while (t--) {

		printf("Case %d:\n", ++cas);

		scanf("%d%d%d", &n, &k, &qw);

		for (int i = 2; i <= k; i++)

			scanf("%d", &need[i]);

		build(1, n);

		char op[15];

		int a, b, c;

		while (qw--) {

			scanf("%s%d%d", op, &a, &b);

			if (op[0] == 'W') {

				scanf("%d", &c);

				add(a, b, c);

			} else printf("%d\n", query(a, b));

		}

		printf("\n");

	}

	return 0;

}