单点修改+区间查询

I Hate It

题目背景

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

题目描述

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

输入格式

第一行，有两个正整数 \(n\) 和 \(m\)（\(0<n \le 2\times 10^5,0<m<5000\)），分别代表学生的数目和操作的数目。学生 ID 编号分别从 \(1\) 编到 \(n\)。

第二行包含 \(n\) 个整数，代表这 \(n\) 个学生的初始成绩，其中第 \(i\) 个数代表 ID 为 \(i\) 的学生的成绩。

接下来有 \(m\) 行。每一行有一个字符 \(c\)（只取 Q 或 U），和两个正整数 \(a\)，\(b\)。

• 当 \(c\) 为 Q 的时候，表示这是一条询问操作，它询问 ID 从 \(a\) 到 \(b\)（包括 \(a,b\)） 的学生当中，成绩最高的是多少；
• 当 \(c\) 为 U 的时候，表示这是一条更新操作，如果当前 \(a\) 学生的成绩低于 \(b\)，则把 ID 为 \(a\) 的学生的成绩更改为 \(b\)，否则不改动。

输出格式

对于每一次询问操作输出一行一个整数，表示最高成绩。

样例 #1

样例输入 #1

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

样例输出 #1

5
6
5
9
```#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int tr[N<<2],tag[N<<2],a[N];
struct segment_tree{
	void push_up(int i){
		tr[i]=max(tr[i<<1],tr[i<<1|1]);
	}
	
	void build(int i,int l,int r){
		if(l==r){
			tr[i]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(i<<1,l,mid);
		build(i<<1|1,mid+1,r);
		push_up(i);
	}
	
	void f(int i,int k){
		tag[i]+=k;
		tr[i]=max(tr[i],k);
	}
	
	void push_down(int i,int l,int r){
		if(tag[i]){
			int mid=(l+r)>>1;
			f(i<<1,tag[i]);
			f(i<<1|1,tag[i]);
			tag[i]=0;
		}
	}
	
	void update(int i,int L,int R,int t,int x){
		if(L==R){
			if(tr[i]<x)tr[i]=x;
			return;
		}
		push_down(i,L,R);
		int mid=(L+R)>>1;
		if(t<=mid)update(i<<1,L,mid,t,x);
		else update(i<<1|1,mid+1,R,t,x);
		push_up(i);
	}
	
	int query(int i,int L,int R,int l,int r){
		if(l<=L&&r>=R){
			return tr[i];
		}
		push_down(i,L,R);
		int ans=0;
		int mid=(L+R)>>1;
		if(l<=mid){
			int t=query(i<<1,L,mid,l,r);
			ans=max(ans,t);
		}
		if(r>mid){
			int t=query(i<<1|1,mid+1,R,l,r);
			ans=max(ans,t);
		}
		return ans;
	}
}ST;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	ST.build(1,1,n);
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		int x,y;
		cin>>x>>y;
		if(c=='Q'){
			int ans=ST.query(1,1,n,x,y);
			cout<<ans<<"\n";
		}else{
			ST.update(1,1,n,x,y);
		}
	}
	return 0;
}