HDU 3954

```/*
* 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;
}

```

HDU 3954

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

10 hdu

http://acm.hdu.edu.cn/showproblem.php?pid=3038 题意：[1-n]的区间，有m个询问，每个询问表示[a,b
http://acm.hdu.edu.cn/showproblem.php?pid=4862 #include <iostream> #include <cstdio&
http://acm.hdu.edu.cn/showproblem.php?pid=3376 题意：一个矩阵，每个点有价值，起点左上角终点右
http://acm.hdu.edu.cn/showproblem.php?pid=4861 两个人进行游戏，桌上有k个球，第i个球的值为1^i+
http://acm.hdu.edu.cn/showproblem.php?pid=2501&PHPSESSID=fme1u1rdulrni3r4tbv5t5e186 递推分析
KIDx 的解题报告 HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728 对于代码31行
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 7553 Accepted: 3599 De

Problem Description PusherBoy is an online game http://www.hacker.org/push . There is an R *