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

HDU 4027

发表于: 2012-02-04   作者:digiter   来源:转载   浏览次数:
摘要: 线段树变种 在2logn段上面做文章,swap(x, y)太阴了... /* * Author: rush * Filename: segment_sum2.cpp * Timestamp: 2012-02-04 19:12:20 CST */ #include <cstdio> #include <cstring> #include
线段树变种
在2logn段上面做文章,swap(x, y)太阴了...

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