题目：I Hate It

一个基础的线段树模板，单点修改+区间查询

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#define ls(x) x<<1

#define rs(x) x<<1|1

const int N=2e5+5;

using namespace std;

int n,m,a[N];

namespace segment

{

	struct smt

	{

		int l,r,v;

		smt(int ll,int rr,int vv)

		{

			l=ll;r=rr;v=vv;

		}

		smt(){

		}

	}e[N<<2];

	void update(int x)

	{

		e[x].v=max(e[ls(x)].v,e[rs(x)].v);

	}

	void build(int x,int l,int r)

	{

		e[x].l=l,e[x].r=r;

		if(l==r)

		{

			e[x]=smt(l,r,a[l]);

			return ;

		}

		int mid=(e[x].l+e[x].r)>>1;

		build(ls(x),l,mid);

		build(rs(x),mid+1,r);

		update(x);

	}

	void modify(int x,int l,int v)

	{

		if(e[x].l==l && e[x].r==l)

		{

			e[x].v=max(e[x].v,v);

			return ;

		}

		int mid=(e[x].l+e[x].r)>>1;

		if(l<=mid)

		    modify(ls(x),l,v);

		else

		    modify(rs(x),l,v);

		update(x);

	}

	int query(int x,int l,int r)

	{

		if(l<=e[x].l && e[x].r<=r)

		    return e[x].v;

		int mid=(e[x].l+e[x].r)>>1,ret=-1e9;

		if(l<=mid)

		    ret=max(ret,query(ls(x),l,r));

		if(r>mid)

		    ret=max(ret,query(rs(x),l,r));

		return ret;

	}

}

using namespace segment;

int main()

{

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++)

	    scanf("%d",&a[i]);

	build(1,1,n);

	while(m--)

	{

		char opt[2];

		int l,r;

		scanf("%s %d %d",opt,&l,&r);

		if(*opt=='Q')

		    printf("%d\n",query(1,l,r));

		else

		    modify(1,l,r);

	}

	return 0;

}

2022春每日一题：Day 41的相关教程结束。