I Hate It

HDOJ-1754

这道题是线段树简单的入门题，只是简单考察了线段树的基本使用，建树等操作。
这里需要注意的是输入要不使用scanf要不使用快速输入。
这里的maxs数组需要开大一点，4倍是最稳妥的，一定不会溢出。
区间查询的时候要注意if后不是之间使用else应该分开写，因为两个区间可能是相交的。

//单点更新，单点查询

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

const int maxn=200005;

const int INF=0X3F3F3F3F;

int n,m;

int maxs[maxn<<2];

int a[maxn];

void pushup(int id,int l,int r){

    int lc=id<<1;

    int rc=id<<1|1;

    maxs[id]=max(maxs[lc],maxs[rc]);

}

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

    if(l==r){

        maxs[id]=a[l];

        return;

    }

    int lc=id<<1;

    int rc=id<<1|1;

    int mid=(l+r)>>1;

    build(lc,l,mid);

    build(rc,mid+1,r);

    pushup(id,l,r);//向上维护

}

void update(int id,int l,int r,int p,int v){

    if(l==r&&l==p){

        maxs[id]=v;

        return;

    }

    int mid=(l+r)>>1;

    int lc=id<<1;

    int rc=id<<1|1;

    if(p<=mid){

        update(lc,l,mid,p,v);

    }else{

        update(rc,mid+1,r,p,v);

    }

    pushup(id,l,r);

}

int query(int id,int l,int r,int p,int q){

    int maxss=-INF;

    if(p<=l&&q>=r){

        return maxs[id];

    }

    int mid=(l+r)>>1;

    if(p<=mid){

        maxss=max(maxss,query(id<<1,l,mid,p,q));

    }

    if(q>mid){

        maxss=max(maxss,query(id<<1|1,mid+1,r,p,q));

    }

    return maxss;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    while(cin>>n>>m){

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

            cin>>a[i];

        }

        build(1,1,n);

        for(int i=0;i<m;i++){

            char c;int a1,b1;

            cin>>c>>a1>>b1;

            if(c=='U'){//更新

                update(1,1,n,a1,b1);

            }else{//查询

                cout<<query(1,1,n,a1,b1)<<endl;

            }

        }

    }

    return 0;

}

巴特西

HDOJ-1754(线段树+单点更新)

I Hate It

HDOJ-1754

最新文章

热门文章