HDU 1754線分ツリー

9688 ワード
セグメントツリー

タイトルリンク:


[kuangbin君を連れて飛ぶ]特集七線分樹B-I Hate It

Description


多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.これは多くの学生に反感を抱かせた.あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.

Input


この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第1行には、2つの正の整数NおよびM(0)があり、それぞれ学生の数および操作の数を表す.学生ID番号はそれぞれ1編からNまでです.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数はIDがiの学生の成績を表す.次はM行です.各行には、1文字C(Q’またはU’のみ)と、2つの正の整数A,Bがある.Cが‘Q’である場合、これはAからB(A,Bを含む)までのIDの学生の中で、成績が最も高いものはどれくらいかを尋ねる質問操作であることを示す.Cが‘U’である場合、IDがAの学生の成績をBに変更するように要求する更新操作であることを示す.

Output


問合せ操作ごとに、1行に最高成績を出力します.

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

構想:線分の木、区間の最値を求めて、


奇妙なタイムアウトで、後の2人は他の人のコードを見て、入力部分が違います.
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:
", minimum_length);
        printf("%*c
%*s

", minimum_length, 'A', minimum_length, "ABC");    // *  
    }

    return 0;
}

以下は本スラグで書かれていますが、不思議なことにタイムアウトからACのコードが変わりました.rm -rf ./
/************************************************************************* > File Name: hdu_1754.cpp > Author: dulun > Mail: [email protected] > 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
", query(x,y, 1));
            }
        }
    }


    return 0;
}
Pythonの道5:集合
HDU2020