- 浏览: 118391 次
- 性别:
- 来自: 北京
最新评论
线段树变种,也是在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; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1151/** * @brief Finds the ... -
HDU 4027
2012-02-04 22:09 849线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 887写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 970转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1188封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 797终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1137源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 803import java.util.*; import j ... -
整数划分
2010-10-07 10:38 839#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 980// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1050typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1291Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 775static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 877标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 848“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1039“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1004推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1185/* * Author: rush * Creat ...
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
自己做的HDU ACM已经AC的题目
HDU图论题目分类
hdu 1005.比较简单的一道题,有兴趣的可以看看。