初版代码
一开始码的是普通暴力 因为维护区间内的最大值实在没想到什么好的方法
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define il inline
#define Inf 0x3f3f3f3f
int n,m;
int a[N];
il int read()
{
int x=0;
bool f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=0;
for(;isdigit(ch);ch=getchar())
x=(x<<1)+(x<<3)+ch-'0';
return f?x:(~(x-1));
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
{
char op;
cin>>op;
if(op=='Q')
{
int x,y;
x=read();y=read();
int ans=-Inf;
for(int j=x;j<=y;j++)
{
if(ans<a[j])
ans=a[j];
}
cout<<ans<<"\n";
}
else
{
int x,y;
x=read();y=read();
if(a[x]<y)a[x]=y;
}
}
return 0;
}
然后 然后 然后就AC了？？？
好吧 那么有没有什么更高级的解法呢
线段树
观察到题目要求单点修改 区间维护最大值
运用线段树能很好的做到这一点
将线段树的部分操作改为求最大值即可
标签：ch,P1531,int,线段,read,讲解,define,Hate,getchar From： https://www.cnblogs.com/pigAlg/p/17547606.html