题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1754
题目不难,不过开始我犯了一个低级错误,输入n,m,m代表操作的数目,我没有写了,写代码的时候,就感觉有问题,不过那时不知怎么的了,糊涂了,
就是while(m--)我没有写了,就错了,我一直在考虑,哪里错了想了很久,一直WA 后来看了一遍题目才知道犯了一个如此低级,改了,AC,不过,在想
为什么WA的时候,我想到一个问题,就是如果把最大的改成很小,即小于第二大的就可以了,那输出的时候还是那个最大的我举个例子。
例如:
我的AC代码,测出来的数据
输入:
4 3
1 2 3 4
Q 1 4
U 4 2
Q 1 4
输出
4
4
按题目意思输出应该为
输出
4
3
但是
输出
4
4
的过了,难道是题目的测试数据,不够全面吗?
要是输出该为
输出
4
3
的话 要如何做呢,我想了一下,还没想出来,谁想出来了,多多指教,将感激不尽!
把最大的改成很小,即小于第二大的就可以了,那么如何更新最大的了呢!//只有这里会出问题 ,其他的地方没有。
我的AC代码
#include<stdio.h>
#include<iostream>
#define MAXSIZE 200005 using namespace std;
struct node
{
int left,right,m;
}tree[MAXSIZE*4];
void build(int node,int left,int right)
{
tree[node].left=left;
tree[node].right=right;
tree[node].m=0;
if(left==right)
return ;
int mid=(left+right)/2;
build(node*2,left,mid);
build(node*2+1,mid+1,right);
}
void update(int node,int pos,int val)
{
tree[node].m=max(val,tree[node].m);
if(tree[node].left==pos&&tree[node].right==pos)
return ;
int mid=(tree[node].left+tree[node].right)/2;
if(pos<=mid) update(node*2,pos,val);
else
update(node*2+1,pos,val);
}
int query(int node,int left,int right)
{
if(tree[node].left==left&&tree[node].right==right)
return tree[node].m;
int mid=(tree[node].left+tree[node].right)/2;
if(right<=mid)
return query(node*2,left,right);
else if(left>mid)
return query(node*2+1,left,right);
else
return max( query(node*2,left,mid), query(node*2+1,mid+1,right) );
}
int main(void)
{
int n,m,i,j,k,l;
int x,y;
char c;
while(scanf("%d%d",&n,&m)==2)
{
build(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
update(1,i,x);
}
getchar();
while(m--)
{
scanf("%c",&c);
scanf("%d%d",&x,&y);
getchar();
if(c=='Q')
{
printf("%d\n",query(1,x,y));
}
else if(c=='U')
{
update(1,x,y);
}
}
}
return 0;
}