HDU 1754 I Hate It //线段树单点更新

悠悠 2022-09-20 15:27 169阅读 0赞

# I Hate It #

**Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 36738 Accepted Submission(s): 14481**

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

Author

linle

Source

[2007省赛集训队练习赛（6）\_linle专场][2007_6_linle]

Recommend

lcy | We have carefully selected several similar problems for you: [1166][] [1698][] [1542][] [1394][] [2795][]

#include <stdio.h>
    
    struct node 
    {
    	int l, r;
    	int max;
    }tree[500005];
    int h[200005];
    int max;
    
    int MAX(int a, int b)
    {
    	if(a>b)
    		return a;
    	return b;
    }
    void build(int l, int r, int n)
    {
    	int mid;
    	tree[n].l = l, tree[n].r = r;
    	if(l==r)
    	{
    		tree[n].max = h[l];
    		return ;
    	}
    	mid = (l + r)/2;
    
    	build(l, mid, 2*n);
    	build(mid+1, r, 2*n+1);
    
    	tree[n].max = MAX(tree[n*2].max, tree[n*2+1].max);
    }
    void up(int a, int k, int n)
    {
    	int mid, w;
    	if(tree[n].l==tree[n].r && tree[n].l==a)
    	{
    		tree[n].max = k;
    		w = n/2;
    		while(w)
    		{
    			tree[w].max = MAX(tree[w*2].max, tree[w*2+1].max);
    			w /= 2;
    		}
    		return;
    	}
    
    	mid = (tree[n].l + tree[n].r)/2;
    	if(a <= mid)
    		up(a, k, 2*n);
    	else
    		up(a, k, 2*n+1);
    }
    void qu(int l, int r, int n)
    {
    	int mid;
    	if(tree[n].l==l && tree[n].r==r)
    	{
    		max = MAX(max, tree[n].max);
    		return ;
    	}
    	mid = (tree[n].l + tree[n].r)/2;
    
    	if(l >= mid+1)
    		qu(l, r, 2*n+1);
    	else if(r <= mid)
    		qu(l, r, 2*n);
    	else
    	{
    		qu(l, mid, 2*n);
    		qu(mid+1, r, 2*n+1);
    	}			
    }
    
    int main()
    {
    	int n, m;
    	int i, a, b;
    	char ch[10];
    
    	while(scanf("%d%d", &n, &m) != -1)
    	{
    		for(i=1; i<=n; i++)
    			scanf("%d", &h[i]);
    		build(1, n, 1);
    
    		while(m--)
    		{
    			scanf("%s", ch);
    			scanf("%d%d", &a, &b);
    			if(ch[0]=='Q')
    			{
    				max = -0xfffff;
    				qu(a, b, 1);
    				printf("%d\n", max);
    			}
    			else
    				up(a, b, 1);
    		}
    	}
    
    	return 0;
    }

[2007_6_linle]: http://acm.hdu.edu.cn/search.php?field=problem&key=2007%CA%A1%C8%FC%BC%AF%D1%B5%B6%D3%C1%B7%CF%B0%C8%FC%A3%A86%A3%A9_linle%D7%A8%B3%A1&source=1&searchmode=source
[1166]: http://acm.hdu.edu.cn/showproblem.php?pid=1166
[1698]: http://acm.hdu.edu.cn/showproblem.php?pid=1698
[1542]: http://acm.hdu.edu.cn/showproblem.php?pid=1542
[1394]: http://acm.hdu.edu.cn/showproblem.php?pid=1394
[2795]: http://acm.hdu.edu.cn/showproblem.php?pid=2795