【HDU1754】I Hate It(线段树)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 09 月 20 日

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩

题意:给一组数据,让快速查找某区间最大值,有更新操作。
题解:赤裸裸的线段树。

#include <stdio.h>
#include <string.h>
#define RR(X) ((X)<<1)+1
#define LL(X) (X)<<1
#define maxlen 200005
struct Node {
	int l,r;
	int m;
}nodes[4*maxlen];
int scores[maxlen];
int max(int a,int b){return a>b?a:b;}
int buildTree(int l,int r,int n){
	nodes[n].l=l;
	nodes[n].r=r;
	nodes[n].m=0;
	if(l==r) {
		return nodes[n].m=scores[l];
	};
	int mid=(l+r)>>1;
	return nodes[n].m=max(buildTree(l,mid,LL(n)),buildTree(mid+1,r,RR(n)));
}
int query(int l,int r,int n){
	if(nodes[n].l==l && nodes[n].r==r){
		return nodes[n].m;
	}
	if(r<=nodes[LL(n)].r)
		return query(l,r,LL(n));
	else if(l>=nodes[RR(n)].l)
		return query(l,r,RR(n));
	else {
		return max(query(l,nodes[LL(n)].r,LL(n)),query(nodes[RR(n)].l,r,RR(n)));
	}
}
int updata(int l,int r,int n,int num){
	if(nodes[n].l==l && nodes[n].r==r){
		return nodes[n].m=num;
	}
	if(l>=nodes[RR(n)].l)
		return nodes[n].m=max(nodes[LL(n)].m,updata(l,r,RR(n),num));
	else if(r<=nodes[LL(n)].r)
		return nodes[n].m=max(updata(l,r,LL(n),num),nodes[RR(n)].m);
	else return nodes[n].m=max(updata(l,nodes[LL(n)].r,LL(n),num),updata(nodes[RR(n)].l,r,RR(n),num));
}

int main()
{
	//freopen("1.txt","r",stdin);
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(scores,0,sizeof(scores));
		for (int i=1;i<=n;i++)
			scanf("%d",&scores[i]);
		buildTree(1,n,1);
		char t[10];
		int a,b;
		for(int i=1;i<=m;i++)
		{
			scanf("%s%d%d",t,&a,&b);
			if(t[0]=='Q') printf("%d\n",query(a,b,1));
			else updata(a,a,1,b);
		}
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日