描述：某次列車途經(jīng)C個城市，城市編號依次為1到C，列車上共有S個座位，鐵路局規(guī)定售出的車票只能是坐票，即車上所有的旅客都有座。售票系統(tǒng)是由計算機執(zhí)行的，每一個售票申請包含三個參數(shù)，分別用O、D、N表示，O為起始站，D為目的地站，N為車票張數(shù)。售票系統(tǒng)對該售票申請作出受理或不受理的決定，只有在從O到D的區(qū)段內(nèi)列車上都有N個或N個以上的空座位時該售票申請才被受理。請你寫一個程序，實現(xiàn)這個自動售票系統(tǒng)。
題目就是要求實現(xiàn)兩種操作，1、求一段區(qū)間的最大值/最小值；2、給一段區(qū)間上的每一個數(shù)加上一個值。
對于區(qū)間，理應(yīng)想到線段樹。而線段樹是十分靈活的，幾乎每道題目都不一樣，其中關(guān)于要在結(jié)點中保存哪些信息的問題就值得思考。
要快速地查詢區(qū)間最值，首先考慮用seg[i].max表示該區(qū)間內(nèi)的最大值，這樣一來，執(zhí)行“給[a,b]區(qū)間每個數(shù)增加d”的時候，只需要遞歸到一個完整的被覆蓋著的區(qū)間，將這個區(qū)間的max增加d即可，回溯時更新父結(jié)點。但是這么做是有問題的，某個被覆蓋過的區(qū)間以上的區(qū)間信息確實沒有問題，但是它以下呢？max值是不能夠向下傳遞的！所以需要增加區(qū)間信息。
給出如下結(jié)果：
1、seg[i].max表示結(jié)點i表示的區(qū)間的最大值；
2、seg[i].cover表示結(jié)點i表示的區(qū)間被某個售票申請直接覆蓋的數(shù)量
這樣一來，需要統(tǒng)計某個已經(jīng)被覆蓋的區(qū)間的子結(jié)點的信息時，將cover所包含的信息向下傳遞即可。因為cover是可以向下傳遞的：一個區(qū)間的值全部增加d，它的子結(jié)點的值也必然全部增加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 閱讀(961)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)