HDU 1754 I Hate It 线段树

本文主要是介绍HDU 1754 I Hate It 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 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

题解：当然是线段树，不过下面的两种代码差别还挺大的。

对于有些静态RMQ，它给予了初始的状态，则可以根据所有状态一次性建造线段树,

而像有些未给定初始状态，只是每次会添加一些信息的，可以开始时只建空树。

1046MS：

#include <iostream>
using namespace std;
#define N 200005
struct item
{
int l, r, num;
} node[N*3];
int max ( int a, int b )
{
return a > b ? a : b;
}
void build ( int l, int r, int u )
{
node[u].l = l;
node[u].r = r;
node[u].num = 0;
if ( l == r ) return;
int mid = ( l + r ) >> 1;
build ( l, mid, u << 1 );
build ( mid + 1, r, (u<<1) + 1 );
}
void update ( int pos, int val, int u )
{
if ( node[u].l == pos && node[u].r == pos )
{
node[u].num = val;
return;
}
int mid = ( node[u].l + node[u].r ) >> 1;
if ( pos <= mid )
update ( pos, val, u << 1 );
else 
update ( pos, val, (u << 1) + 1 );
node[u].num = max ( node[u<<1].num, node[(u<<1)+1].num );
}
int query ( int l, int r, int u )
{
if ( node[u].l == l && r == node[u].r )
return node[u].num;
int mid = ( node[u].l + node[u].r ) >> 1;
if ( r <= mid )
return query ( l, r, u << 1 );
else if ( l > mid )
return query ( l, r, ( u << 1 ) + 1 );
else
return max ( query ( l, mid, u << 1 ), query ( mid + 1, r, (u << 1 ) + 1 ) );
}
int main()
{
char ch[3];
int n, m, score, a, b;
//freopen("a.txt","r",stdin);
while ( scanf("%d%d",&n,&m) != EOF )
{
build ( 1, n, 1 );
for ( int i = 1; i <= n; ++i )
{
scanf("%d",&score);
update ( i, score, 1 ); 
}
while ( m-- )
{	
scanf( "%s %d %d", ch, &a, &b );
if ( ch[0] == 'Q' )
printf( "%d\n", query ( a, b, 1 ) );
else
update ( a, b, 1 );
}	
}
return 0;
}

500MS

#include <iostream>
using namespace std;
#define N 200005
int score[N];
struct item
{
int l, r, num;
} node[N*3];
int max ( int a, int b )
{
return a > b ? a : b;
}
void build ( int l, int r, int u )
{
node[u].l = l;
node[u].r = r;
if ( l == r )
{
node[u].num = score[l];
return;
}
int mid = ( l + r ) >> 1;
build ( l, mid, u << 1 );
build ( mid + 1, r, (u<<1) + 1 );
node[u].num = max ( node[u<<1].num, node[(u<<1)+1].num );
}
void update ( int pos, int val, int u )
{
if ( node[u].l == pos && node[u].r == pos )
{
node[u].num = val;
return;
}
int mid = ( node[u].l + node[u].r ) >> 1;
if ( pos <= mid )
update ( pos, val, u << 1 );
else 
update ( pos, val, (u << 1) + 1 );
node[u].num = max ( node[u<<1].num, node[(u<<1)+1].num );
}
int query ( int l, int r, int u )
{
if ( node[u].l == l && r == node[u].r )
return node[u].num;
int mid = ( node[u].l + node[u].r ) >> 1;
if ( r <= mid )
return query ( l, r, u << 1 );
else if ( l > mid )
return query ( l, r, ( u << 1 ) + 1 );
else
return max ( query ( l, mid, u << 1 ), query ( mid + 1, r, (u << 1 ) + 1 ) );
}
int main()
{
char ch[3];
int n, m, a, b;
//freopen("a.txt","r",stdin);
while ( scanf("%d%d",&n,&m) != EOF )
{
for ( int i = 1; i <= n; ++i )
scanf("%d",score+i);
build ( 1, n, 1 );
while ( m-- )
{	
scanf( "%s %d %d", ch, &a, &b );
if ( ch[0] == 'Q' )
printf( "%d\n", query ( a, b, 1 ) );
else
update ( a, b, 1 );
}	
}
return 0;
}

这篇关于HDU 1754 I Hate It 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---