ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋    

 

题目地址:

  http://acm.hdu.edu.cn/showproblem.php?pid=1754

题目描述:

  

I Hate It

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6306    Accepted Submission(s): 2267


Problem 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
Hint
Huge input,the C function scanf() will work better than cin
 

 

感觉好久没有A题了 , 最近一直没有状态,  豆豆也转行了, 郁闷.......    因为打算 专精 数据结构方面,

所以这几天一直都在复习 数据结构, 再一次学习了 线段树, 以前只会用它来 更新点 求和 , 现在终于水了一

个 RMQ 的裸题了, HAPPY 一下....

对于 RMQ 的题目, 看PPT 上面的 DP 我直接0rz了...........表示DP只会做水题.... 这方面还是交给

YCH 吧.   不过看了 shǎ崽 大神 博客的 线段树专辑后, 发现 用线段树处理 这类问题 非常方便, 修改查询

都是 O (logN)的 ,  稍稍优化了下输入, 234MS AC ........

 

代码如下 :

代码
/*
Coded By  : MiYu
Link      : 
http://www.cnblogs.com/MiYu  || http://www.cppblog.com/MiYu
Author By : MiYu
Test      : 1
Program   : 1754
*/
//#pragma warning( disable:4789 )
#include 
<iostream>
#include 
<algorithm>
#include 
<string>
#include 
<set>
#include 
<map>
#include 
<utility>
#include 
<queue>
#include 
<stack>
#include 
<list>
#include 
<vector>
#include 
<cstdio>
#include 
<cstdlib>
#include 
<cstring>
#include 
<cmath>
using namespace std;
inline 
int max ( int a, int b ){
    
return a > b ? a : b;
}
typedef 
struct seg_Tree {
    
int left, right;
    
int mid() { return (left+right)>>1; }
    
int max;
}S;
S seg[
605000];
int key[200010];
int creat ( int left, int right, int root = 1 ){
    seg[root].left 
= left;    
    seg[root].right 
= right; 
    
if ( left == right )
        
return seg[root].max = key[left];
    
int mid = seg[root].mid();
    
return seg[root].max = max ( creat ( left, mid, root << 1 ),creat ( mid + 1, right, ( root << 1 ) + 1 ) );
}

void modify ( int val, int pos, int r = 1 ){
    
if ( seg[r].left == seg[r].right ){
        seg[r].max 
= val;
        
return;
    }
    
int mid = seg[r].mid();
    
if ( pos <= mid ){
        modify ( val, pos, r 
<< 1 );
    } 
else {
        modify ( val, pos, ( r 
<< 1 ) + 1 );
    }
    seg[r].max 
= max ( seg[r<<1].max, seg[ (r<<1+ 1 ].max );
}

int quy ( int left, int right, int r = 1 ){
    
if ( seg[r].left == left && seg[r].right == right ){
        
return seg[r].max;
    }
    
int mid = seg[r].mid();
    
if ( right <= mid  ){
        
return quy ( left, right, r << 1 );
    } 
else if ( left > mid ) {
        
return quy ( left, right, (r << 1+ 1 );
    } 
else {
        
return max ( quy ( left, mid, r << 1 ), quy ( mid + 1, right, (r << 1+ 1 ) );
    }
}
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, x, y;
    
while ( scan_d(N) && scan_d(M) ){
        
for ( int i = 1; i <= N; ++ i ){
            scan_d( key[i] );    
        }
        creat ( 
1, N );  
        while ( M -- ){
            
char ask[5];
            scanf ( 
"%s", ask );
            scan_d(x);
            scan_d(y);
            
switch ( ask[0] ){
                
case 'Q':    printf ( "%d\n", quy ( x,y ) );
                            
break;
                
case 'U':    modify ( y, x );
            }
        }
    }
    
return 0;
}

/*
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
*/


 

 



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理