题目

蒟蒻wa掉(样例)的程序

#include<bits/stdc++.h>
using namespace std;
struct tree 
{
	int l;//左子节点编号 
	int r;//右... 
	int w;//该点的值 
}d[1000010];
int a[1000010];
int h=1;
int n,m; 

void build(int s,int t,int me) {
  if (s==t) { //如果到底了，就记上 
    d[me].w=a[s];
    return;
  }
  
  int m=s+((t-s)>>1); 
  d[me].l=++h;//先记左节点 
  build(s,m,d[me].l);//递归建左子树 
  d[me].r=++h;//记右节点 
  build(m+1,t,d[me].r);//递归建右子树 
  d[me].w=max(d[d[me].l].w,d[d[me].r].w);//该点为左右节点的最大值 
}

int change(int l,int r,int u,int v,int me)
{
	//[l,r]表示你现在所在区间，你要把u点值改为v,me表示现在所在的点 
	if(l==u && r==u)
		{
			d[u].w=v;
			return d[u].w;
		}
	int m=l+((r-l)>>1);
	int k;
	if(m<u)//如果左子节点编号小于u,说明左子树节点都小于u 
	{
		k=change(m+1,r,u,v,d[me].r);//遍历右子树 
		k=max(d[me].l,k);//由于右子树值更新，所以重新比一遍 
	}
	else
	{ 
		k=change(l,m,u,v,d[me].l);//否则遍历左子树 
		k=max(d[me].r,k); //... 
	} 
	d[me].w=k;
	return d[me].w;//返回该子节点的值，用于父节点比较 
}

int finding(int l, int r, int s, int t, int me) {
	//[l,r]表示你要找的区间，[s,t]表示现在所查的区间,me表示现在所在的点 
  if (l<=s && t<=r)
  { 
    return d[me].w;//到底了，就返回这个值 
  }
  int m=s+((t-s)>>1),sum=-90000;
  
  if(l<=m) 
  	sum=max(sum,finding(l,r,s,m,d[me].l));//比较 
  if(r>m) 
  	sum=max(sum,finding(l,r,m+1,t,d[me].r));//比较，防止左右端点都包括在内的情况 
  return sum;
}


int main()
{
	cin>>n>>m;
	for(register int i=1;i<=n;++i)//初始化 
		{
			d[i].l=d[i].r=-1;
			d[i].w=-1;
		}
	
	for(register int i=1;i<=n;++i)
		{
			cin>>a[i];
		}
	
	build(1,n,1);//建树
	 
	for(register int i=1;i<=m;++i)
		{
			char x;
			cin>>x;
			int u,v;
			cin>>u>>v;
			if(x=='U')
			{
				change(1,n,u,v,1);
			}
			else 
			{ 
				cout<<finding(u,v,1,n,1)<<endl;
			}
		}
	while(1);
	return 0;
}