描述：某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票，即车上所有的旅客都有座。售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N为车票张数。售票系统对该售票申请作出受理或不受理的决定，只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序，实现这个自动售票系统。
题目就是要求实现两种操作，1、求一段区间的最大值/最小值；2、给一段区间上的每一个数加上一个值。
对于区间，理应想到线段树。而线段树是十分灵活的，几乎每道题目都不一样，其中关于要在结点中保存哪些信息的问题就值得思考。
要快速地查询区间最值，首先考虑用seg[i].max表示该区间内的最大值，这样一来，执行“给[a,b]区间每个数增加d”的时候，只需要递归到一个完整的被覆盖着的区间，将这个区间的max增加d即可，回溯时更新父结点。但是这么做是有问题的，某个被覆盖过的区间以上的区间信息确实没有问题，但是它以下呢？max值是不能够向下传递的！所以需要增加区间信息。
给出如下结果：
1、seg[i].max表示结点i表示的区间的最大值；
2、seg[i].cover表示结点i表示的区间被某个售票申请直接覆盖的数量
这样一来，需要统计某个已经被覆盖的区间的子结点的信息时，将cover所包含的信息向下传递即可。因为cover是可以向下传递的：一个区间的值全部增加d，它的子结点的值也必然全部增加d。
以下是我的代码：
#include<stdio.h>
#define maxn 60007
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define max(a,b) (a>b?a:b)
struct
{
long a,b;
long max,cover;
}seg[maxn*3];
long n,s,m;
void build(long node,long x,long y)
{
long mid=(x+y)>>1;
seg[node].a=x;seg[node].b=y;
seg[node].max=seg[node].cover=0;
if(x<y)
{
build(L(node),x,mid);
build(R(node),mid+1,y);
}
}
bool ok(long node,long x,long y,long d)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
bool re=false,cal=false;
if(x<=a&&b<=y)
return (seg[node].max+d<=s);
if(seg[node].cover>0)
{
seg[L(node)].cover+=seg[node].cover;
seg[R(node)].cover+=seg[node].cover;
seg[L(node)].max+=seg[node].cover;
seg[R(node)].max+=seg[node].cover;
seg[node].cover=0;
seg[node].max=max(seg[L(node)].max,seg[R(node)].max);
}
if(mid>=x)
{
re=ok(L(node),x,y,d);
cal=true;
}
if(mid+1<=y)
re=((re||!cal)&&ok(R(node),x,y,d));
return re;
}
void insert(long node,long x,long y,long d)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
if(x<=a&&b<=y)
{
seg[node].max+=d;
seg[node].cover+=d;
}
else
{
if(mid>=x)
{
insert(L(node),x,y,d);
seg[node].max=max(seg[node].max,seg[L(node)].max);
}
if(mid+1<=y)
{
insert(R(node),x,y,d);
seg[node].max=max(seg[node].max,seg[R(node)].max);
}
}
}
int main()
{
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
scanf("%ld%ld%ld",&n,&s,&m);
build(1,1,n-1);
while(m--)
{
long a,b,d;
scanf("%ld%ld%ld",&a,&b,&d);
if(ok(1,a,b-1,d))
{
printf("YES\n");
insert(1,a,b-1,d);
}
else printf("NO\n");
}
return 0;
}
posted on 2010-02-24 08:38
lee1r 阅读(870)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构