首页 > 代码库 > 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(线段树,简单,不过好像有点问题)