传送门:点击打开链接
题意:
有n青蛙和m蚊子(n,m<=1e5),青蛙两个参数,位置xi,舌头长度ti
蚊子两个参数,位置pj,权值bj
只有当xi+ti>=pj时,第i只青蛙才能吃到第j只蚊子。
如果第j只蚊子能被多只青蛙吃到,那么xi最小的青蛙会把这只蚊子吃了
每次青蛙吃了某只蚊子以后,ti会增加蚊子的bj
输出n只青蛙吃的蚊子数,以及最后时候的舌头长度ti
蚊子两个参数,位置pj,权值bj
只有当xi+ti>=pj时,第i只青蛙才能吃到第j只蚊子。
如果第j只蚊子能被多只青蛙吃到,那么xi最小的青蛙会把这只蚊子吃了
每次青蛙吃了某只蚊子以后,ti会增加蚊子的bj
输出n只青蛙吃的蚊子数,以及最后时候的舌头长度ti
蚊子会按照给出的时间顺序出现。
思路:我们先来考虑另一个问题
1.如何在[1,n]区间内找到最靠近左边的位置使得权值>=x
2.如何在[l,r]区间内找到最靠近左边的位置使得权值>=x
对于第一种,应该是比较熟悉的了,直接构建线段树维护最大值,然后查询的时候先考虑左子树,如果左子树的最大值>=x就往左边走,否则就往右边走。复杂度O(logn)
对于第二种,好像就没那么好维护了,然而我们仔细分析一下发现其实有单调性,可以考虑用二分来做
我们可以用线段树维护区间内权值最大值,然后用二分去枚举区间的右节点,查询[l,m]的最大值是否>=x,然后将它组逐渐向左边靠近即可