GroupBlog

题目链接：

[kuangbin带你飞]专题七线段树　B - I Hate It

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

思路：线段树，求区间最值，

莫名奇妙超时，后俩看别人代码，输入部分不一样，

scanf("%c%d%d", &o, &x, &y);//我是这样写的

getchar();
scanf("%c%d%d", &o, &x, &y);//有的人这样写
scanf("%*c%c%d %d", &o, &x, &y);//有的人这样写的，我改成这样,结果莫名奇妙AC。。。
//"%*c%c%d %d"

后来问了度娘
scanf(“%* s”)表示跳至下一空白字符，这里主要是中间的*字符起的作用。比如说

int n;
    scanf("%*d %*d %d",&n);
    printf("%d",n);
    return 0;
    //如果输入2004 2005 2006 那么n=2006 
    //*的标准解释是滞后赋值

还有这个的：动态控制显示格式用的，运行下下面的代码就明白了：
程序代码：


#include <stdio.h>

int main(int argc, char* argv[]) {
    int minimum_length;

    for (minimum_length = 1; minimum_length < 6; minimum_length++) {
        printf("Minimum length %d:\n", minimum_length);
        printf("%*c\n%*s\n\n", minimum_length, 'A', minimum_length, "ABC");    // * 用来表示一个整数值
    }

    return 0;
}

下面是本渣渣写的，莫名莫名奇妙就从超时变AC的代码。rm -rf ./

/*************************************************************************
    > File Name: hdu_1754.cpp
    > Author: dulun
    > Mail: dulun@xiyoulinux.org
    > Created Time: 2016年03月21日 星期一 22时33分58秒
 ************************************************************************/

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 200086;
int a[N];
struct Node
{
    int l, r, mxc;
};
Node t[2000000];

void build(int l, int r, int d)
{
    t[d].l = l;
    t[d].r = r;
    if(l == r)
    {
        t[d].mxc = a[l];
        return;
    }
    int m = (l + r) / 2;

    build(l, m, d<<1);
    build(m+1, r, (d<<1)+1);

    t[d].mxc = max(t[d<<1].mxc, t[(d<<1)+1].mxc);
}

int change(int id, int num, int d)
{
    if(t[d].l == id && t[d].r == id)
    {
        return t[d].mxc = num;
    }

    int m = (t[d].l + t[d].r) / 2;
    if( id <= m ) return t[d].mxc = max(t[d<<1|1].mxc, change(id, num, d<<1));
    else return t[d].mxc = max(t[d<<1].mxc, change(id, num, d<<1|1));
}

int query(int l, int r, int d)
{
    if(t[d].l == l && t[d].r == r)
    {
        return t[d].mxc;
    }
    int m = (t[d].l + t[d].r) / 2;
    if(r <= m) return query(l, r, d<<1);
    if(l > m) return query(l, r, (d<<1)+1);
    return max(query(l, m, d<<1), query(m+1, r, (d<<1)+1));
}


int main()
{

    int n, k;
    while(~scanf("%d%d", &n, &k))
    {
        memset(a, 0, sizeof(a));
        memset(t, 0, sizeof(t));
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        build(1, n, 1);
        for(int i = 0; i < k; i++)
        {
            char o;
            int x, y;
            scanf("%*c%c%d %d", &o, &x, &y);//?????????
            if(o == 'U')
            {
                a[x] = y;
                change(x, y, 1);
            }
            if(o == 'Q')
            {
                printf("%d\n", query(x,y, 1));
            }
        }
    }


    return 0;
}