描述：某次列車途經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 閱讀(952)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構