线段树 0 pts

Link

code:

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int maxn=2e5+10;
ll n,m,a[maxn],op,x,y;
struct SegmentTree{
	ll l,r;
	ll st,nd,tag;
	SegmentTree(){l=r=st=nd=tag=0;}
}t[maxn<<2];
void build(ll p,ll l,ll r){
	t[p].l=l,t[p].r=r;
	if(l==r){t[p].st=t[p].nd=a[l];return;}
	ll mid=l+r>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].st=max(t[p*2].st,t[p*2+1].st);
	t[p].nd=min(t[p*2].st,t[p*2+1].st);
}
void pushdown(ll p){
	if(t[p].tag){
		t[p].st=max(t[p*2].st,t[p*2+1].st);
		t[p].nd=min(t[p*2].st,t[p*2+1].st);
		t[p].tag=0;
	}
}
void change(ll p,ll k,ll d){
	if(t[p].l==t[p].r){
		t[p].st=t[p].nd=d;
		t[p*2].tag=t[p*2+1].tag=1;
		return;
	}
	pushdown(p*2);
	pushdown(p*2+1);	
	ll mid=t[p].l+t[p].r>>1;
	if(k<=mid)change(p*2,k,d);
	else change(p*2+1,k,d);
	t[p].st=max(t[p*2].st,t[p*2+1].st);
	t[p].nd=min(t[p*2].st,t[p*2+1].st);
}
ll query(ll p,ll l,ll r){// max
	if(l<=t[p].l&&r>=t[p].r)return t[p].st;
	pushdown(p*2);
	pushdown(p*2+1);
	ll mid=t[p].l+t[p].r>>1;
	ll val=LLONG_MIN;
	if(l<=mid)val=max(val,query(p*2,l,r));
	if(r>mid)val=max(val,query(p*2+1,l,r));
	return val;
}
ll calc(ll p,ll l,ll r){
	return min(query(p*2,l,r),query(p*2+1,l,r));
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		cin>>op>>x>>y;
		if(op==1)change(1,x,y);
		if(op==2)cout<<query(1,x,y)<<"\n";
	}
	return 0;
}
/*
5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

*/