注意到后面的总是可以把前面的覆盖掉，所以考虑总是先确定后面的人的位置，这样题目给出的位置pos就变成了"寻找一个位置，使得这个位置左边的空位置数目为pos"，以第一个样例为例：
把样例倒过来之后是这样的：
2 69
1 33
1 51
0 77
先考虑69号，它的pos是2，说明它插入的时候需要队伍前面有2个人，这样，它就在2号位置上了（从0开始）；
再考虑33号，它的pos是1，说明它插入的时候需要队伍前面有1个人，这样，它就在1号位置上了；
再考虑51号，它的pos是1，说明它插入的时候需要队伍前面有1个人，这样，它就在3号位置上了；
再考虑77号，它的pos是0，说明它插入的时候需要队伍前面有0个人，这样，它就在0号位置上了。
嗯，所以开一个empty数组，结点p表示[l,r]区间内的空位置的数目。
不需要query函数，只需要update函数更新就行
Read full article from POJ 2828 Buy Tickets (线段树) | Shoutmon
No comments:
Post a Comment