I hate it （线段树）

B - I Hate It

Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u

cid=83215#status//B/0" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="display:inline-block; position:relative; padding:0px; margin-right:0.1em; vertical-align:middle; overflow:visible; text-decoration:none; font-family:Verdana,Arial,sans-serif; font-size:1em; border:1px solid rgb(211,211,211); color:rgb(85,85,85)">Status

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

Sample Output

Hint

Huge input,the C function scanf() will work better than cin

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 200005

#define inf 0x3f3f3f3f

int sum[maxn<<2],ll[maxn<<2],rr[maxn<<2];

int a[maxn];

inline void pushup(int i){

    sum[i]=max(sum[i<<1],sum[(i<<1)|1]);

}

void build(int l,int r,int i){

    ll[i]=l;

    rr[i]=r;

    if(l==r){

        sum[i]=a[l];

        return;

    }

    int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;

    build(l,m,ls);

    build(m+1,r,rs);

    pushup(i);

}

void update(int k,int v,int i){

    if(ll[i]==rr[i]){

        sum[i]=v;

        return ;

    }

    int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;

    if(k<=m)update(k,v,ls);

    else update(k,v,rs);

    pushup(i);

}

int query(int l,int r,int i){

    if(l<=ll[i]&&rr[i]<=r){

        return sum[i];

    }

    int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;

    int ans=0;

    if(l<=m)ans=max(query(l,r,ls),ans);

    if(m<r)ans=max(query(l,r,rs),ans);

    return ans;

}

int main()

{

    int n,m;

    int u,v;

    //freopen("in.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){

        for(int i=1;i<=n;i++){

            scanf("%d",&a[i]);

        }

        build(1,n,1);

        char q[2];

        while(m--){

            scanf("%s %d %d",q,&u,&v);       //用c会出问题

            if(q[0]=='Q'){

                printf("%d\n",query(u,v,1));

            }

            else {

                update(u,v,1);

            }

        }

    }

}

巴特西

I hate it （线段树）

最新文章

热门文章