題目鏈接
題意：k個等級，n個英雄，每個等級升級有一定經驗，每次兩種操作，一個區間加上val，這樣區間內英雄都獲得當前等級*val的經驗，另一個操作詢問區間經驗最大值
思路：由於等級少，所以每個結點用Max[10]記錄下每個等級的最大值，如果有一個升級就一直找到底，因為一個英雄升級最多10次，所以這個操作最多就10W次可以接受，剩下就是普通的區間修改區間查詢的延遲操作了
代碼：
#include#include #include 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; }
