本文主要是介绍hdu 1754 I Hate It（线段树，单点更新，区间最值），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是求一个线段中的最大数。
线段树的模板题，试用了一下交大的模板。效率有点略低。
代码：
#include <stdio.h>
#include <string.h>
#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b)
{return a > b ? a : b;
}int Cover[TREE_SIZE], Top[TREE_SIZE];class IntervalTree
{
private:int size;int _Query(int a, int b, int l, int r, int Ind){if (a <= l && b >= r)return Top[Ind];int mid = (l + r) >> 1, ret = Cover[Ind];if (a <= mid)ret = max(ret, _Query(a, b, l, mid, Ind << 1));if (b > mid)ret = max(ret, _Query(a, b, mid + 1, r, (Ind << 1) + 1));return ret;}void _Modify(int a, int l, int r, int Ind, int d){if (l == r && l == a){Cover[Ind] = Top[Ind] = d;return ;}int mid = (l + r) >> 1;if (a <= mid)_Modify(a, l, mid, Ind << 1, d);else_Modify(a, mid + 1, r, (Ind << 1) + 1, d);Top[Ind] = max(Top[Ind << 1], Top[(Ind << 1 )+ 1]);}
public:IntervalTree(){memset(Cover, 0, sizeof(Cover));memset(Top, 0, sizeof(Top));size = (TREE_SIZE >> 2) - 1;}IntervalTree(int s){memset(Cover, 0, sizeof(Cover));memset(Top, 0, sizeof(Top));size = s;}int Query(int a, int b){return _Query(a, b, 1, size, 1);}void Modify(int a, int d){return _Modify(a, 1, size, 1, d);}
};int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALint n, m;while (scanf("%d%d", &n, &m) == 2){IntervalTree T(n);for (int i = 1; i <= n; i++){int tmp;scanf("%d", &tmp);T.Modify(i, tmp);}for (int i = 0; i < m; i++){getchar();char ch;int a, b;scanf("%c%d%d", &ch, &a, &b);//printf("%c%d%d\n", ch,a,b);if (ch == 'Q'){printf("%d\n", T.Query(a, b));continue;}if (ch == 'U'){T.Modify(a, b);continue;}}}return 0;
}
update：
2015.4.21
学习这种漂亮的写法：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int maxn = 200000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);int maxPoint[maxn << 2];
void pushup(int rt)
{maxPoint[rt] = max(maxPoint[rt << 1], maxPoint[rt << 1 | 1]);
}void build(int lo, int hi, int rt)
{if (lo == hi){scanf("%d", &maxPoint[rt]);return;}int mi = (lo + hi) >> 1;build(lson);build(rson);pushup(rt);
}void update(int pos, int num, int lo, int hi, int rt)
{if (lo == hi){maxPoint[rt] = num;return;}int mi = (lo + hi) >> 1;if (pos <= mi)update(pos, num, lson);elseupdate(pos, num, rson);pushup(rt);
}int query(int L, int H, int lo, int hi, int rt)
{if (L <= lo && hi <= H){return maxPoint[rt];}int mi = (lo + hi) >> 1;int res = 0;if (L <= mi)res = max(res, query(L, H, lson));if (mi < H)res = max(res, query(L, H, rson));return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALint n, m;while (~scanf("%d%d", &n, &m)){build(1, n, 1);while (m--){char op[2];int a, b;scanf("%s%d%d", op, &a, &b);if (op[0] == 'Q')printf("%d\n", query(a, b, 1, n, 1));elseupdate(a, b, 1, n, 1);}}return 0;
}
这篇关于hdu 1754 I Hate It（线段树，单点更新，区间最值）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
