HDU 3954

线段树变种，也是在2logn段上面做文章

/*
 * Author: rush
 * Filename: hdu3954.cpp
 * Timestamp: 2012-02-04 23:26:50 CST
 */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <sstream>
#define OUT(x) cerr << #x << ": " << (x) << endl
#define SZ(x) ((int)x.size())
#define FOR(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long LL;

int T, N, K, QW;
int need[12];

// Segment Tree for Max
// Accepted: hdu1166, hdu1754, hdu1394, hdu2795
// Accepted: hdu1698, pku3468, pku2528
template<class Data>
struct SegmentTreeMax {
#define LSON t * 2 + 1, a, (a + b) / 2
#define RSON t * 2 + 2, (a + b) / 2 + 1, b
	// 0) NONE: 0x3f3f3f3f, 1LL << 62, (~0ULL >> 1), 1.0e300, -1
	static const Data NONE = -0x3f3f3f3f;
	// 1) OP: x = y, x = (x != NONE ? x + y : y)
	inline void OP(Data &x, Data y) { x = (x != NONE ? x + y : y); }
	inline void OP2(Data &x, Data y) { if (x != NONE) x += y; }
	// 2) INF: 0x3f3f3f3f, (~0U >> 1), 1LL << 62, (~0ULL >> 1), 1.0e300
	static const Data INF = 0x3f3f3f3f;
		
	vector<Data> lazy, node[12];
	void init(int N) {
		lazy.assign(N * 4 + 5, NONE);
		node[0].assign(N * 4 + 5, 0);
		for (int k = 1; k < K; ++k)
			node[k].assign(N * 4 + 5, NONE);
	}
	void up(int t) {
		FOR(k, K) node[k][t] = max(node[k][t * 2 + 1], node[k][t * 2 + 2]);
	}
	void down(int t) {
		if (lazy[t] != NONE) {
			OP(lazy[t * 2 + 1], lazy[t]);
			OP(lazy[t * 2 + 2], lazy[t]);
			FOR(k, K) OP2(node[k][t * 2 + 1], lazy[t] * (k + 1));
			FOR(k, K) OP2(node[k][t * 2 + 2], lazy[t] * (k + 1));
			lazy[t] = NONE;
		}
	}
	void maintain(int k, int t, int a, int b) {
		if (a == b) {
			while (k < K - 1 && node[k][t] >= need[k]) {
				node[k + 1][t] = node[k][t];
				node[k][t] = NONE;
				++k;
			}
		} else {
			down(t);
			if (node[k][t * 2 + 1] >= need[k]) maintain(k, LSON);
			if (node[k][t * 2 + 2] >= need[k]) maintain(k, RSON);
			up(t);
		}
	}
	void update(int x, int y, Data delta, int t, int a, int b) {
		if (x <= a && b <= y) { // inside
			OP(lazy[t], delta);
			for (int k = K - 1; k >= 0; --k) {
				OP2(node[k][t], delta * (k + 1));
				if (k < K - 1 && node[k][t] >= need[k]) {
					maintain(k, t, a, b);
				}
			}
		} else if (a <= y && x <= b) { // overlap
			down(t);
			update(x, y, delta, LSON);
			update(x, y, delta, RSON);
			up(t);
		}
	}
	Data queryValue(int x, int y, int t, int a, int b) {
		if (x <= a && b <= y) { // inside
			for (int k = K - 1; k >= 0; --k)
				if (node[k][t] != NONE) return node[k][t];
		} else if (a <= y && x <= b) { // overlap
			down(t);
			Data ans = -INF;
			ans = max(ans, queryValue(x, y, LSON));
			ans = max(ans, queryValue(x, y, RSON));
			up(t);
			return ans;
		}
		return -INF;
	}
};

SegmentTreeMax<int> st;
int main() {
	scanf("%d", &T);
	for (int id = 1; id <= T; ++id) {
		scanf("%d%d%d", &N, &K, &QW);
		FOR(k, K - 1) scanf("%d", &need[k]);
		st.init(N);
		printf("Case %d:\n", id);
		while (QW--) {
			char cmd[8];
			int x, y, e;
			scanf("%s", cmd);
			if (cmd[0] == 'W') {
				scanf("%d%d%d", &x, &y, &e);
				st.update(x, y, e, 0, 1, N);
			} else {
				scanf("%d%d", &x, &y);
				int ans = st.queryValue(x, y, 0, 1, N);
				printf("%d\n", ans);
			}
		}
		printf("\n");
	}
	return 0;
}