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