P1531 I Hate It

文章目录

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P1531

---

D e s c r i p t i o n Description Description

写一种数据结构，要求支持单点修改和查询区间最值

数据范围： n ≤ 2 × 1 0 6 , m ≤ 5 × 1 0 3 n\leq 2\times 10^6,m\leq 5\times 10^3 n≤2×106,m≤5×103

---

S o l u t i o n Solution Solution

线段树裸题

时间复杂度： O ( ( n + m ) log ⁡ n ) O((n+m)\log n) O((n+m)logn)

---

C o d e Code Code

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 200010 
using namespace std;int n,x,y,m,a[N];
char s[5];
struct xds
{
	#define lson k<<1
	#define rson k<<1|1
	int maxn[N<<2];
	inline void build(int k=1,int l=1,int r=n)
	{
		if(l==r) return (void)(maxn[k]=a[l]);
		int mid=l+r>>1;
		build(lson,l,mid);build(rson,mid+1,r);
		return (void)(maxn[k]=max(maxn[lson],maxn[rson]));
	}
	inline void Modify(int x,int d,int k=1,int l=1,int r=n)
	{
		if(l==r) return (void)(maxn[k]=max(maxn[k],d));
		int mid=l+r>>1;
		if(x<=mid) Modify(x,d,lson,l,mid);
		else Modify(x,d,rson,mid+1,r);
		return (void)(maxn[k]=max(maxn[lson],maxn[rson]));
	}
	inline int Query(int ql,int qr,int k=1,int l=1,int r=n)
	{
		if(ql<=l&&r<=qr) return maxn[k];
		int res=0,mid=l+r>>1;
		if(ql<=mid) res=max(res,Query(ql,qr,lson,l,mid));
		if(qr>mid) res=max(res,Query(ql,qr,rson,mid+1,r));
		return res;
	}
}T;
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
signed main()
{
	n=read();m=read();
	for(register int i=1;i<=n;i++) a[i]=read();
	T.build();
	while(m--)
	{
		scanf("%s",s);x=read();y=read();
		if(s[0]=='Q') printf("%d\n",T.Query(x,y));
		else T.Modify(x,y);
	}
}