HDU-1754-I Hate It(线段树,简单,不过好像有点问题)

时间:2021-10-26 21:27:37

题目链接

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;

}