50分,跪求帮助!!!
查看原帖
50分,跪求帮助!!!
539342
Vuglar_zuo楼主2023/8/4 21:00

大佬帮看看……50分求助

#include<bits/stdc++.h>
using namespace std;
struct data{
	int l,r,x;
}total[8000001];
void build(int l,int r,int id)
{
	total[id].l=l;
	total[id].r=r;
	if(l==r){
		cin>>total[id].x;
		return;
	}
	int m=(l+r)/2;
	build(l,m,id*2);
	build(m+1,r,id*2+1);
	total[id].x=max(total[id*2].x,total[id*2+1].x);
}
void update(int x,int y,int id)
{
	if(total[id].l==total[id].r)
	{
		total[id].x=y;
		return;
	}
	int m=(total[id].l+total[id].r)/2;
	if(x<=m)update(x,y,id*2);
	else update(x,y,id*2+1);
	total[id].x=max(total[id*2].x,total[id*2+1].x);
}
int query(int l,int r,int id)
{
	if(total[id].l>=l&&total[id].r<=r)return total[id].x;
	int maxx=0,m=(total[id].l+total[id].r)/2;
	if(l<=m)maxx=max(maxx,query(l,r,id*2));
	if(r>m)maxx=max(maxx,query(l,r,id*2+1));
	return maxx;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	while(cin>>n>>m)
	{
		int a,b;
		char c;
		build(1,n,1);
		for(int i=1;i<=m;i++)
		{
			cin>>c>>a>>b;
			if(c=='Q')cout<<query(a,b,1)<<endl;
			else update(a,b,1);
		}
	}
	return 0;
}

样例过了(线段树)

2023/8/4 21:00
加载中...