欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu1754线段树

程序员文章站 2022-03-22 19:07:21
...

添加链接描述

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=2e5+5;
int a[maxn];
struct segtree{
	int val;
}st[maxn<<2];
void pushup(int rt){
	st[rt].val =max(st[rt<<1].val ,st[rt<<1|1].val );
}
void build(int l,int r,int rt){
	if(l==r){
		st[rt].val =a[l];
		return;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	pushup(rt);
}
void update(int L,int C,int l,int r,int rt){
	if(l==r){
		st[rt].val =C;
		return;
	}
	int m=(l+r)>>1;
	if(L<=m) update(L,C,l,m,rt<<1);
	else update(L,C,m+1,r,rt<<1|1);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		return st[rt].val ;
	}
	if(L>r||R<l) return 0;
	int m=(l+r)>>1;
//	int m1,m2;
//	m1=m2=0;
//	if(L<=m) m1=query(L,R,l,m,rt<<1);
//	if(R>m) m2=query(L,R,m+1,r,rt<<1|1);
//	return max(m1,m2);
	return max(query(L,R,l,m,rt<<1),query(L,R,m+1,r,rt<<1|1));
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		build(1,n,1);
		char ch;
		int A,B;
		for(int i=1;i<=m;i++){
			getchar();
			scanf("%c%d%d",&ch,&A,&B);
			if(ch=='Q'){
				printf("%d\n",query(A,B,1,n,1));
			}
			if(ch=='U'){
				update(A,B,1,n,1);
			}
		}
	}
	return 0;
}
相关标签: 进阶课程