hdu 1754 I Hate It

题意：给你N个数，M个操作，操作分两类。

(1)"QAB“，查询区间[A,B]内的最大值。

(2)"UAB"，将第A个数的值改成B。

线段树-单点更新。


// Time 843ms; Memory 6448K  

// Time 843ms; Memory 6448K[cpp] view plaincopyprint?#include<iostream>   
#include<cstdio>   
#define maxn 1<<19   
#define inf 1<<30   
  
using namespace std;  
  
int size,n,sm,al[5010];  
struct line  
{  
    int l,r;  
    int n;  
}a[maxn];  
  
void init()  
{  
    int i;  
    for(n=1;n<size;n<<=1);  
    for(i=n;i<2*n;i++)   
    {  
        a[i].l=a[i].r=i-n+1;  
        a[i].n=-inf;  
    }  
    for(i=n-1;i>0;i--)  
    {  
        a[i].l=a[2*i].l;  
        a[i].r=a[2*i+1].r;  
        a[i].n=-inf;  
    }  
}  
void insert(int i,int x,int m)  
{  
    if(x>=a[i].l && x<=a[i].r && a[i].n<m) a[i].n=m;  
    if(a[i].l==a[i].r) return;  
    int mid=(a[i].l+a[i].r)/2;  
    if(x>mid) insert(2*i+1,x,m);  
    else insert(2*i,x,m);  
}  
void find(int x,int y,int i)  
{  
    if(x==a[i].l && y==a[i].r)  
    {  
        if(sm<a[i].n)  
            sm=a[i].n;  
        return;  
    }  
    if(a[i].l==a[i].r) return;  
    int mid=(a[i].l+a[i].r)/2;  
    if(x>mid) find(x,y,2*i+1);  
    else if(y<=mid) find(x,y,2*i);  
    else   
    {  
        find(x,mid,2*i);  
        find(mid+1,y,2*i+1);  
    }  
}  
int main()  
{  
    int j,k,t,x,y,m;  
    char s;  
    while(scanf("%d%d",&size,&t)!=EOF)  
    {  
        init();  
        for(j=0;j<size;j++)  
        {  
            scanf("%d",&k);  
            insert(1,j+1,k);  
        }  
        k=0;  
        for(j=0;j<t;j++)  
        {  
            scanf(" %c",&s);  
            if(s=='U')  
            {  
                scanf("%d%d",&x,&m);  
                insert(1,x,m);  
            }  
            else   
            {  
                scanf("%d%d",&x,&y);  
                sm=-inf;  
                find(x,y,1);  
                al[k++]=sm;  
            }  
        }  
        for(j=0;j<k;j++) printf("%d\n",al[j]);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,