HELP TREE!
查看原帖
HELP TREE!
519092
阿宁已被领养楼主2022/8/12 09:13

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;
}
2022/8/12 09:13
加载中...