40分qwq
虽然我不会单点修改但是我这样做错了到底是什么问题
求调qwq
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll n,m,a[1000000],x,y;
char s;
struct gs
{
ll l,r,num,j,gool;
}shu[1000000];
void build(ll l,ll r,ll g)
{
shu[g].l=l;
shu[g].r=r;
if(l==r)
{
shu[g].num=a[l];
return ;
}
ll mid=(l+r)/2;
build(l,mid,g*2);
build(mid+1,r,g*2+1);
shu[g].num=max(shu[g*2].num,shu[g*2+1].num);
}
void cd(ll g,ll num,ll gool)//传递
{
if(shu[g].l==gool&&shu[g].r==gool)
{
shu[g].num=num;
return ;
}
if(shu[g].l<=gool&&shu[g].r>=gool)
{
shu[g].gool=gool;
shu[g].j=num;
shu[g].num=max(num,shu[g].num);
return ;
}
}
ll count(ll l,ll r,ll g,ll ans)//寻找最大值
{
if(shu[g].l>=l&&shu[g].r<=r) return shu[g].num;
if(shu[g].gool!=0) cd(g*2,shu[g].j,shu[g].gool);
if(shu[g].gool!=0) cd(g*2+1,shu[g].j,shu[g].gool);
shu[g].j=0;
shu[g].gool=0;
ll mid=(shu[g].l+shu[g].r)/2;
if(l<=mid) ans=max(ans,count(l,r,g*2,0));
if(r>mid) ans=max(ans,count(l,r,g*2+1,0));
return ans;
}
void change(ll gool,ll num,ll g)//改变最大值
{
shu[g].gool=gool;
shu[g].j=num;
shu[g].num=max(num,shu[g].num);
return ;
}
int main()
{
//freopen("P1531_2.in","r",stdin);
//freopen("ans.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,n,1);
for(ll i=1;i<=m;i++)
{
cin>>s;
scanf("%lld%lld",&x,&y);
//cout<<i<<' '<<"s="<<s<<' '<<"x="<<x<<' '<<"y="<<y<<endl;
if(s=='Q') printf("%lld\n",count(x,y,1,0));
if(s=='U') if(a[x]<y) {a[x]=y;change(x,y,1);}
}
return 0;
}