当前位置:首页 > 数据结构 > 线段树 > 正文
SSOJ2617售票系统
4224+

题目大意:列出经过m个站点,车上有n个座位,有q个人去买票,告诉你起点和终点以及购票数,请判断是否有足够的票卖给他。

题目描述

某次列车途经C个城市,城市编号依次为1到C,列车上共有S个座位,铁路局规定售出的车票只能是坐票,即车上所有的旅客都有座。售票系统是由计算机执行的,每一个售票申请包含三个参数,分别用O、D、N表示,O为起始站,D为目的地站,N为车票张数。售票系统对该售票申请作出受理或不受理的决定,只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序,实现这个自动售票系统。

输入

第一行包含三个用空格隔开的整数C、S和R,其中1≤C≤100000, l≤S≤100000,1≤R≤100000。C为城市个数,S为列车上的座位数,R为所有售票申请总数。接下来的R行每行为一个售票申请,用三个由空格隔开的整数O,D和N表示,O为起始站,D 为目的地站,N为车票张数,其中1≤D≤C,1≤O≤C,所有的售票申请按申请的时间从早到晚给出。

输出

输出共有R行,每行输出一个“YES”或“NO”,表示当前的售票申请被受理或不被受理。

样例输入

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

样例输出

YES
YES
NO
NO

提示

买票数量在1到9999之间,10个点数据范围:5, 10, 100, 500, 1000, 5000, 10000, 30000, 50000, 70000, 100000

解题思路

暴力:开一个数组f记录各个站点的售票数,处理请求时,对区间[x,y)进行加票数,如果发现票数超过座位数,就输出NO,并且把票减回去。时间复杂度O(n*q)。

线段树做法:购买[x,y)区间的票,我们可以先查询这个区间的最大票数k,如果k+购票数z不超过座位数,那就输出YES,并且整个区间增加z,否则输出NO。当然,如果你不想写查询函数,也可以先加再判断:先整个区间增加z,然后判断根结点([1,n]最大值)是否超过座位数,超过的话再减回去。

程序实现

线段树紧凑存储:区间加票数,区间求最大值。标记不下放,可以这样处理——d记录区间记录儿子结点的最大值(还没加标记),回溯时d[p]求法请见代码13行,儿子结点之所以要加上f,是因为该区间根结点也还没有整段加标记;第8行也是这样,整段修改,只需要修改标记,因为d记录的是还没加标记的最大值。

线段树(f标记子树没加):只加不查,并不是真的不查,因为区间加后,回溯的时候会自动更新父亲结点的最大值,加完后我们判断根结点是否超过总票数即可,超过就减回去。

线段树(f标记儿子没加):标记下放。线段的意义不一样,做法也不一样。d记录的是区间的最大值,f记录的是儿子还没加的数,因此修改的时候,既要该d,也要该f,回溯更新父亲结点的时候,只需要看儿子结点的d,而不需要管标记。但是用到儿子结点时,如果父亲有标记,需要先下放。

当然,f标记儿子没加,也可以不下放标记,只需要在更新的时候注意转移就行(6、11行)。

对于可以叠加的标记,可以不写下放;标记既可以标记儿子没加,也可以标记子树没加。如果子树没加,那么d不需要加自己的标记,d也不是区间和、区间最大值,要加上标记才是;如果儿子没加,d就需要加上自己的标记,即父亲结点已加,只是儿子还没加。对于会互相影响的标记,如赋值、多个标记,那就需要写标记下放了。

暴力模拟:6万随机数据1s勉强过,10万随机数据2秒勉强过。

SSOJ2617售票系统:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!