P1531 I Hate It

链接：Miku

-----------------------

线段树水题

单点修改+区间最大值查询

-------------------------

这道题比板子很简单，因为懒标记不用写

为什么呢，懒标记什么时候用？我们要修改的区间完全覆盖了某个区间的时候

全是单点修改还能覆盖谁？只有他自己啊。

那还懒什么，懒不了

-------------------------

因为在洛谷上的要求是大于原来的成绩再修改，所以我们修改的时候还要加个判断

至于初始化，就当作是把那个点成绩修改了就好，毕竟没有负数成绩，所以肯定比0大

----------------------------

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
long long sum[800002], lazy[800005];

char f;
int x,y;
long long k;
void pushup(int x){
    sum[x]=max(sum[x << 1],sum[x << 1 | 1]);
    return;
}
void update(int x, int l, int r, int L, int R, long long d){
    if (L <= l && r <= R){
        sum[x] = max(sum[x],d) ;
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) update(x << 1, l, mid, L, R, d);
    if (R > mid) update(x << 1 | 1, mid + 1, r, L, R, d);
    pushup(x);
}
long long query(int x, int l, int r, int L, int R){
    if (L <= l && r <= R){
        return sum[x];
    }
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (L <= mid) ans=max(ans,query(x << 1, l, mid, L, R));
    if (R > mid) ans= max(ans,query(x << 1 | 1, mid + 1, r, L, R));
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        update(1, 1, n, i, i, x);
    }
    for(int i=1;i<=m;++i){
        cin>>f;
        if(f=='U'){
            scanf("%d%d",&x,&k);
            update(1, 1, n, x, x, k);
        }
        else{
            scanf("%d%d",&x,&y);
            printf("%lld
", query(1, 1, n, x, y));
        }
    }
    return 0;
}