又被爆踩。

　　　　正解写挂。

　　　　暴力不会。

　　　　只会改题。

　　　　还要加油。

　　　　T1

　　　　　　$nlog^2$是显然的

　　　　　　那么考虑只二分一次，就$nlog$了！

　　　　　　有什么能通过一次二分$O(1)$得到呢？

　　　　　　二分a的位置，$O(1)$得到b的位置

　　　　　　check的特判极其惨烈，%%%$Rock_B$调出来了

　　　　　　

　　　　　　另一种简单一点的做法：

　　　　　　二分查找不好搞，考虑另一个二分——分治

　　　　　　通过分治，让每次的询问参数减半，也是$O(logn)$的复杂度

　　　　　　设计一个函数找到a的长度为lena，b的长度为lenb时，排名为rank的元素

　　　　　　那么把每次询问的rank分成一半，在a，b中找到对应的位置（长度不够则让另一个串多分一点）

　　　　　　如果$a[k/2]<b[k/2]$，则可知$a[1]～a[k/2]$都不可能成为排名为rank的元素

　　　　　　因为把ab放一起排序后$a[k/2]$后面的元素太多了..显然一定多于$lena+lenb-rank$

　　　　　　所以把$a[1]~a[k/2]$直接排除出答案，把rank-=k/2（或者当lena<k/2时的lena），递给下一层解决

　　　　T2

　　　　　　一个dp分成两部分

　　　　　　$dp[i]=min(dp[j-1]+value(j,i))$

　　　　　　单调栈维护所有可能贡献出value的j（单调递增栈）

　　　　　　对同一个j维护可能的最大$dp[k-1](k<=j)$，随便用什么数据结构维护栈里的最大值即可。

　　　　T3

　　　　　　为防电脑凸燃关激，存为上策