Beyond the Void
BYVoid
線段樹 售票系統
本文正體字版由OpenCC轉換

這是一個線段樹的經典應用問題,要求維護一個序列,支持對某個區間RMQ(查詢區間最值),支持修改一個區間,使區間中所有數增加某個數值。

在線段樹中修改某個區間的值,爲保證高效,要使用標記向下傳。

下面是楊弋在NOI2008冬令營上的講稿。

線段樹講稿

這是swq大牛的題解

/*
 * Problem: 售票系統
 * Author: Guo Jiabao
 * Time: 2009.3.20 20:51
 * State: Solved
 * Memo: 線段樹修改區間 優化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=60001;
using namespace std;
struct sgt_node
{
	sgt_node *left,*right;
	int a,b,m,v,add;
};
int N,LIM,Q,SS=-1;
sgt_node *sgt_root,SE[MAXN*2];
inline sgt_node* sgt_new(int a,int b)
{
	SE[++SS].m=(a+b)/2;
	SE[SS].a=a;SE[SS].b=b;
	SE[SS].add=SE[SS].v=0;
	SE[SS].left=SE[SS].right=0;
	return &SE[SS];
}
void sgt_create(sgt_node *&p,int a,int b)
{
	p=sgt_new(a,b);
	if (a!=b)
	{
		sgt_create(p->left,a,p->m);
		sgt_create(p->right,p->m+1,b);
	}
}
void sgt_movedown(sgt_node *p)
{
	p->v+=p->add;
	if (p->a!=p->b)
	{
		p->left->add+=p->add;
		p->right->add+=p->add;
	}
	p->add=0;
}
void sgt_edit(sgt_node *p,int a,int b,int delta)
{
	if (p->a==a && p->b==b)
	{
		p->add+=delta;
		sgt_movedown(p);
	}
	else
	{
		sgt_movedown(p->left);
		sgt_movedown(p->right);
		if (b<=p->m)
			sgt_edit(p->left,a,b,delta);
		else if (a>=p->m+1)
			sgt_edit(p->right,a,b,delta);
		else
		{
			sgt_edit(p->left,a,p->m,delta);
			sgt_edit(p->right,p->m+1,b,delta);
		}
		p->v=(p->left->v > p->right->v)?p->left->v:p->right->v;
	}
}
bool sgt_find(sgt_node *p,int a,int b,int delta)
{
	if (p->add)
		sgt_movedown(p);
	if (p->a==a && p->b==b)
		return p->v+delta<=LIM;
	if (b<=p->m)
		return sgt_find(p->left,a,b,delta);
	if (a>=p->m+1)
		return sgt_find(p->right,a,b,delta);
	if (!sgt_find(p->left,a,p->m,delta))
		return false;
	else
		return sgt_find(p->right,p->m+1,b,delta);
}
void init()
{
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	scanf("%d%d%d",&N,&LIM,&Q);
	sgt_create(sgt_root,1,N);
}
void solve()
{
	int i,a,b,c;
	for (i=1;i<=Q;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		b--;
		if (sgt_find(sgt_root,a,b,c))
		{
			sgt_edit(sgt_root,a,b,c);
			printf("YES\n");
		}
		else
			printf("NO\n");
	}
}
int main()
{
	init();
	solve();
	return 0;
}
<div class="MainText">

<strong>【問題描述】</strong>
某次列車途經C個城市,城市編號依次爲1到C,列車上共有S個座位,鐵路局規定售出的車票只能是坐票, 即車上所有的旅客都有座。售票系統是由計算機執行的,每一個售票申請包含三個參數,分別用O、D、N表示,O爲起始站,D爲目的地站,N爲車票張數。售票 系統對該售票申請作出受理或不受理的決定,只有在從O到D的區段內列車上都有N個或N個以上的空座位時該售票申請才被受理。請你寫一個程序,實現這個自動 售票系統。
<p align="left">【輸入格式】
第一行包含三個用空格隔開的整數C、S和R,其中1≤C≤60000, l≤S≤60000,1≤R≤60000。C爲城市個數,S爲列車上的座位數,R爲所有售票申請總數。接下來的R行每行爲一個售票申請,用三個由空格隔開 的整數O,D和N表示,O爲起始站,D 爲目的地站,N爲車票站數,其中1≤D≤C,1≤O≤C,所有的售票申請按申請的時間從早到晚給出。

【輸出格式】
輸出共有R行,每行輸出一個“YES”或“NO”,表示當前的售票申請被受理或不被受理。

【輸入輸出樣例】
<strong>
</strong>輸入:
4 6 4
1 4 2
1 3        2
2 4 3
1 2  3

輸出:
YES
YES
NO
NO</div>

上次修改時間 2017-02-03

相關日誌