# HDU 4027

```/*
* Author: rush
* Filename: segment_sum2.cpp
* Timestamp: 2012-02-04 19:12:20 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;

// Segment Tree for Sum
// Accepted: hdu1166, hdu1754, hdu1394, hdu2795
// Accepted: hdu1698, pku3468, pku2528
template<class Data>
struct SegmentTreeSum {
#define LSON t * 2 + 1, a, (a + b) / 2
#define RSON t * 2 + 2, (a + b) / 2 + 1, b
// 0) NONE: 0x3f3f3f3f, (int)(~0U >> 1), 1LL << 62, (LL)(~0ULL >> 1), 1.0e300
#define NONE -(LL)(~0ULL >> 1)
// 1) OP: x = y, x = (x != NONE ? x + y : y)
inline void OP(Data &x, Data y) { x = y; }

vector<Data> lazy;
vector<Data> node;
vector<int> one;
void init(int N) {
lazy.assign(N * 4 + 5, NONE);
node.assign(N * 4 + 5, 0);
one.assign(N * 4 + 5, false);
}
inline void up(int t) {
node[t] = node[t * 2 + 1] + node[t * 2 + 2];
one[t] = one[t * 2 + 1] && one[t * 2 + 2];
}
void down(int t, int a, int b) {
if (lazy[t] != NONE) {
OP(lazy[t * 2 + 1], lazy[t]);
OP(lazy[t * 2 + 2], lazy[t]);
int k = (a + b) / 2;
OP(node[t * 2 + 1], lazy[t] * (k - a + 1));
OP(node[t * 2 + 2], lazy[t] * (b - (k + 1) + 1));
lazy[t] = NONE;
}
}
void update(int x, int y, Data delta, int t, int a, int b) {
if (x <= a && b <= y) { // inside
OP(lazy[t], delta);
OP(node[t], delta * (b - a + 1));
if (node[t] <= 1LL) one[t] = true;
} else if (a <= y && x <= b) { // overlap
//down(t, a, b);
update(x, y, delta, LSON);
update(x, y, delta, RSON);
up(t);
}
}
bool doMaintain;
void maintain(int t, int a, int b) {
if (a == b) {
const double EPS = 1.0e-9;
node[t] = (LL)sqrt(node[t] + EPS);
if (node[t] <= 1LL) one[t] = true;
} else {
//down(t, a, b);
if (!one[t * 2 + 1]) maintain(LSON);
if (!one[t * 2 + 2]) maintain(RSON);
up(t);
}
}
Data queryValue(int x, int y, int t, int a, int b) {
if (x <= a && b <= y) { // inside
if (doMaintain) maintain(t, a, b);
return node[t];
} else if (a <= y && x <= b) { // overlap
//down(t, a, b);
Data ans = 0;
ans += queryValue(x, y, LSON);
ans += queryValue(x, y, RSON);
up(t);
return ans;
}
return 0;
}
};

int main() {
SegmentTreeSum<LL> st;
int N, M, id = 1;
while (scanf("%d", &N) != EOF) {
st.init(N);
for (int i = 1; i <= N; ++i) {
LL t;
scanf("%I64d", &t);
st.update(i, i, t, 0, 1, N);
}
printf("Case #%d:\n", id++);
scanf("%d", &M);
while (M--) {
int T, X, Y;
scanf("%d%d%d", &T, &X, &Y);
if (X > Y) swap(X, Y);
if (T == 0) {
st.doMaintain = true;
st.queryValue(X, Y, 0, 1, N);
} else {
st.doMaintain = false;
LL ans = st.queryValue(X, Y, 0, 1, N);
printf("%I64d\n", ans);
}
}
printf("\n");
}
return 0;
}
```

HDU 4027

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

KIDx的解题报告 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027 加了输入外挂之后，排
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