【哥种的第一棵线段树，至于你信不信，我反正信了】HDU 1754 I Hate It
http://acm.hdu.edu.cn/showproblem.php?pid=1754Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
效率不错，用加速输入外挂快了2百多ms！！
至于你信不信，我反正信了!!
http://dl.iteye.com/upload/attachment/527565/67b9abbd-f99c-37fd-9b0d-a536c4e4049f.png
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define eps 1e-8#define PI 3.14159265358979#define inf 0x3fffffffstruct node{int l, r, maxs; //一个结点表示一个区间和区间的最大值maxs}N;int v;inline int maxs (int a, int b) //木有inline会慢一点点{return a > b ? a : b;}void create (int u, int l, int r) //创建线段树，设u为父结点{N.l = l, N.r = r;if (l == r){N.maxs = v; //初始化子叶结点return ;}int mid = (l + r) >> 1; //一个区间分为2个，变成左子树和右子树create (u+u, l, mid); //递归建立左子树create (u+u+1, mid+1, r); //递归建立右子树N.maxs = maxs (N.maxs, N.maxs); //返回更新父亲结点的最大值}void update (int u, int id, int New) //更新结点的值，id是结点编号，New是新的值{if (N.l == N.r){N.maxs = New;return ;}if (id <= N.r) //id在左子树上【N是N的左子结点】update (u+u, id, New); //继续递归寻找idelse update (u+u+1, id, New);//id在右子树上【N是N的右子结点】N.maxs = maxs (N.maxs, N.maxs); //递归更新父亲结点的最大值}int find (int u, int start, int end) //寻找这个区间的最大值{ //此函数博大精深，至于你信不信，我反正信了……if (start <= N.l && end >= N.r)return N.maxs;int m1 = -inf, m2 = -inf;if (start <= N.r)m1 = find (u+u, start, end);if (end >= N.l)m2 = find (u+u+1, start, end);return maxs (m1, m2);}inline bool scan_d(int &num) // 加速输入外挂，纯粹复制模板{ char in; bool IsN=false; in=getchar(); if(in==EOF) return false; while(in!='-'&&(in<'0'||in>'9')) in=getchar(); if(in=='-'){ IsN=true;num=0;} else num=in-'0'; while(in=getchar(),in>='0'&&in<='9'){ num*=10,num+=in-'0'; } if(IsN) num=-num; return true;}int main(){int n, m, i, a, b;char ch;while (~scanf ("%d%d", &n, &m)){for (i = 1; i <= n; i++)scan_d (v); //加速输入create (1, 1, n); //创建并初始化线段树，1是根结点while (m--){//scanf ("%s%d%d", ch, &a, &b);scanf ("%s", ch);scan_d (a); //加速输入scan_d (b);if (ch == 'Q') //寻找区间的最大值printf ("%d\n", find (1, a, b));else update (1, a, b); //更新结点的值}} return 0;}
页:
[1]