当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

HDU 3954

发表于: 2012-02-05   作者:digiter   来源:转载   浏览次数:
摘要: 线段树变种,也是在2logn段上面做文章 /* * Author: rush * Filename: hdu3954.cpp * Timestamp: 2012-02-04 23:26:50 CST */ #include <cstdio> #include <cstring> #include <cmath> #inclu
线段树变种,也是在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;
}

HDU 3954

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
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
线段树求矩形面积并 经典题目,poj 1151 是相同的题目。终于学了求矩形面积并,详细说一下。 首先是
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5013 题意: 思路: 这里有错,是Hi(x)=siga
Problem Description PusherBoy is an online game http://www.hacker.org/push . There is an R *
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号