越来越懒,以后水题就懒得写了。。。所以D题起步,C题看心情。。。 AB除非挂了10发+不然不提。。。
好D题题意:
一群买家去拍卖场,给你这群人每次叫价的人的id和价格。问你,在没有其中某些人的情况下,谁最后买走了东西,以什么价格。如果走了人之后是某人连续叫价,那以最低的那个为准。
思路:
就这给一坨数据,然后给一坨查询,一般都是线段树。
首先,我们要问,谁赢了,那就是在走了一些人之后,剩下的人中,最后叫价的那个人。看看规模也知道啦,那就是走的人,把大区间分成一堆小区间,然后求小区间拼起来的区间的最大值,所以就是维护一个区间最大值就好了。因为总共就20w个查询或者20w个人走了,最多就分出20w个区间,如果区间查询是log的,那肯定跑的过。
然后就是要查他用什么价格买走的。就很显然,他的价格比出价第二高的那个人高。所以就找赢家出钱记录中,比第二高的价高的最低价。
找第二高的人,就直接把最高的人也赶走就找到了。
代码:388D