http://acm.hdu.edu.cn/showproblem.php?pid=1698初试线段树，感觉还不错。下面的代码是我超时的代码，作为比较。
#include <iostream>
using namespace std;
struct node
{
int value;
int a,b;
}tree[300010];
int maketree(int i,int a,int b)
{
tree[i].a=a;
tree[i].b=b;
if(a==b)
{
return tree[i].value=1;
}
int mid=(a+b)/2;
return tree[i].value =maketree(2*i,a,mid)+maketree(2*i+1,mid+1,b);
}
int update(int i,int a,int b,int v)
{
if(tree[i].a==tree[i].b)
return tree[i].value =v;
int mid=(tree[i].a+tree[i].b)/2;
if(a>mid) //更新区间为右区间
return tree[i].value=update(2*i+1,a,b,v)+tree[2*i].value;
else if(b<=mid) //更新区间为左区间
return tree[i].value=update(2*i,a,b,v)+tree[2*i+1].value;
else //否则左右区间皆更新
return tree[i].value=update(2*i,a,mid,v)+update(2*i+1,mid+1,b,v);
}
int main()
{
int a,b,t,q,v,i,n;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d",&n);
maketree(1,1,n);
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d",&a,&b,&v);
update(1,a,b,v);
}
printf("Case %d: The total value of the hook is %d.\n",i,tree[1].value);
}
return 0;
}为什么超时呢？因为每次都是更新到最底层，下面的代码进行了优化。上面的v表示整棵树的总值，下面的v表示整棵树的状态，如果是-1，则表示有杂色，否则表示整棵树纯色，值为v，更新时不需要到最底层，计算总值时只需把纯色值*个数加起来，也不需要到最底层。
以下是AC的代码：
#include <iostream>
using namespace std;
struct node
{
int value;
int a,b;
}tree[300010];
void maketree(int i,int a,int b)
{
tree[i].a=a;
tree[i].b=b;
tree[i].value=1;
if(a==b)
{
return ;
}
int mid=(a+b)/2;
maketree(2*i,a,mid);
maketree(2*i+1,mid+1,b);
}
void update(int i,int a,int b,int v)
{
if(tree[i].value==v) //如果该区域内值一样则不用修改
return ;
if(tree[i].a==a && tree[i].b==b )//如果修改区域一样，则直接把该区域的值改为指定值
{
tree[i].value=v;
return ;
}
if(tree[i].value !=-1) //如果是纯色的，而修改区域不一致，则先将其子区域置为父值，对子区域进行操作
{
tree[2*i].value=tree[2*i+1].value=tree[i].value;
tree[i].value =-1; //标记为杂色
}
int mid=(tree[i].a+tree[i].b)/2; //下面一系列行为都是在父区间为杂色时对子区间进行的操作
if(a>mid) //更新区间为右区间
update(2*i+1,a,b,v);
else if(b<=mid) //更新区间为左区间
update(2*i,a,b,v);
else //否则左右区间皆更新
{
update(2*i,a,mid,v);
update(2*i+1,mid+1,b,v);
}
}
int search(int i) //计算总值
{
if(tree[i].value!=-1)
return (tree[i].b-tree[i].a+1)*tree[i].value;
else
return search(i*2)+search(i*2+1);
}
int main()
{
int a,b,t,q,v,i,n;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d",&n);
maketree(1,1,n);
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d",&a,&b,&v);
update(1,a,b,v);
}
printf("Case %d: The total value of the hook is %d.\n",i,search(1));
}
return 0;
}
还有一种更快的方法：判断每个点是否在某更新区间，在则更新，不在不处理，因为前面的会被后面的覆盖，所以我们从后面考虑，倒着做。
AC代码如下：
#include <iostream>
using namespace std;
int data[100005][3];
int main()
{
int t,q,n,i,j,sum,k,v;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d%d",&n,&q);
for(j=1;j<=q;j++)
scanf("%d%d%d",&data[j][0],&data[j][1],&data[j][2]);
sum=0;
for(k=1;k<=n;k++)
{
v=1;
for(j=q;j>=1;j--)
if(data[j][0]<=k && k<=data[j][1])//寻找k所在的更新区间，若存在则更新，不存在v=1不变
{
v=data[j][2]; //若找的最后面的更新区间，则停止，因为前面的会被覆盖
break;
}
sum+=v;
}
printf("Case %d: The total value of the hook is %d.\n",i,sum);
}
return 0;
}
主要还是学习线段树这种高级数据结构，只有多写代码才能熟练掌握线段树的基本操作。
posted on 2011-05-04 23:04
大大木马 阅读(2004)
评论(5) 编辑 收藏 引用