P1531 I Hate It

简单线段树。

只需要单点修改。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5;
int xds[maxn<<2],a[maxn],n,m;
void pushup(int k){
	xds[k]=max(xds[k<<1],xds[k<<1|1]);
}
void build(int k,int l,int r){
	if(l==r){
		xds[k]=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void modify(int k,int l,int r,int x,int y){
	if(l==r){
		xds[k]=max(xds[k],y);
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)modify(k<<1,l,mid,x,y);
	else modify(k<<1|1,mid+1,r,x,y);
	pushup(k);
}
int query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return xds[k];
	int res=-0x3f3f3f3f,mid=l+r>>1;
	if(x<=mid)res=max(res,query(k<<1,l,mid,x,y));
	if(mid<y)res=max(res,query(k<<1|1,mid+1,r,x,y));
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		string c;
		cin>>c;
		int x,y;
	    cin>>x>>y;
		if(c[0]==‘Q‘){
			cout<<query(1,1,n,x,y)<<endl;
		}else{
			modify(1,1,n,x,y);
		}
	}
	return 0;
}

P1531 I Hate It

原文：https://www.cnblogs.com/kkksc0100/p/p1531.html