首页 > 代码库 > HDU-1754-I Hate It（线段树，简单，不过好像有点问题）
HDU-1754-I Hate It（线段树，简单，不过好像有点问题）
题目链接
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;
}
HDU-1754-I Hate It（线段树，简单，不过好像有点问题）