更新区间中的点，维护区间最大值。
以下是我的代码：
#include<stdio.h>
const long maxn=200007,maxm=5007;
typedef struct
{
long a,b,max;
long left,right;
}node;
long n,m,tot,rp[maxn];
node tree[maxn*7];
long max(long a,long b)
{
return (a>b?a:b);
}
void build(long x,long y)
{
long now=++tot,mid=(x+y)>>1;
tree[now].a=x;tree[now].b=y;
if(x==y)
tree[now].max=rp[x];
else if(x<y)
{
tree[now].left=tot+1;build(x,mid);
tree[now].right=tot+1;build(mid+1,y);
tree[now].max=max(tree[tree[now].left].max,tree[tree[now].right].max);
}
}
void insert(long id,long node)
{
long a=tree[node].a,b=tree[node].b,mid=(a+b)>>1;
if(id==a&&id==b)
tree[node].max=max(tree[node].max,rp[id]);
else
{
if(id<=mid)
insert(id,tree[node].left);
else
insert(id,tree[node].right);
tree[node].max=max(tree[tree[node].left].max,tree[tree[node].right].max);
}
}
long getmax(long x,long y,long node)
{
long a=tree[node].a,b=tree[node].b,mid=(a+b)>>1,re=-1;
if(x<=a&&b<=y)
return tree[node].max;
if(mid>=x)
re=max(re,getmax(x,y,tree[node].left));
if(mid+1<=y)
re=max(re,getmax(x,y,tree[node].right));
return re;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%ld%ld",&n,&m)==2)
{
for(long i=1;i<=n;i++) scanf("%ld",&rp[i]);getchar();
tot=0;
build(1,n);
// Build A Segment Tree
for(long i=1;i<=m;i++)
{
char cmd;
long a,b;
//for(long i=1;i<=tot;i++)printf("[%ld,%ld]'max is %ld\n",tree[i].a,tree[i].b,tree[i].max);
cmd=getchar();
scanf("%ld%ld",&a,&b);getchar();
switch(cmd)
{
case 'Q':
if(a>b)
{
long t=a;a=b;b=t;
}
printf("%ld\n",getmax(a,b,1));
break;
case 'U':
rp[a]=b;
insert(a,1);
}
}
}
return 0;
}
posted on 2010-02-18 15:57
lee1r 阅读(482)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构