WA了4个点求助QAQ
查看原帖
WA了4个点求助QAQ
164700
金苹果gold楼主2020/8/7 13:05

怎么回事啊QAQ

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200000+10;
struct Node{
	int l,r;
	int sum;
}tree[4*MAXN];
int a[MAXN],n,m;
char c; 
inline void build(int p,int l,int r)
{
	tree[p].l=l;
	tree[p].r=r;
	if(l==r)
	{
		tree[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].sum=max(tree[p*2].sum,tree[p*2+1].sum);
}
inline void update(int p,int x,int v)
{
	if(tree[p].l==tree[p].r)
	{
		tree[p].sum=v;
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid)
		update(p*2,x,v);
	else
		update(p*2+1,x,v);
	tree[p].sum=max(tree[p*2].sum,tree[p*2+1].sum);
}
inline int q(int p,int l,int r)
{
	if(l<=tree[p].l&&tree[p].r<=r)
		return tree[p].sum;
	int mid=(tree[p].l+tree[p].r)/2;
	if(r<=mid)
		return q(p*2,l,r);
	else if(l>mid)
		return q(p*2+1,l,r);
	else
		return max(q(p*2,l,r),q(p*2+1,l,r));
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	for (int i=1;i<=m;i++){
		cin>>c;
		if(c=='U')
		{
			int x,v;
			scanf("%d%d",&x,&v);
            if(a[x]<v)
			    update(1,x,v);
		}
		else if(c=='Q')
		{
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%d\n",q(1,l,r));
		}
	}
	return 0;
}
2020/8/7 13:05
加载中...