题面 P2617 Dynamic Rankings Solution 这题需要一个比较妙的操作。 首先，我们阅读题面，发现题目要求我们处理区间K大带单点修改的问题。我们考虑用整体二分来解决这个问题。 总所周知，整体二分中的修改只能以“添加”的形式进行，而不能以“覆盖”的方式进行。但这里，我们修改一个位置的数之后，新的数会把原来的数覆盖掉。如果我们不能处理好这个问题，整体二分一定会错。 因此，我们考虑添加一个“删除”操作来解决这个问题。我们可以把这里的修改变为：删除原有的数+加入一个新的数。这样子，我们就把原来的“覆…

题面 P3332 [ZJOI2013]K大数查询 Solution 这是一道不辣么模板的整体二分题。 首先，我们先来假设一下只有一个询问应该怎么搞。 考虑这样做：我们先二分一个答案，修改中，如果所要修改的数大于mid，则在这段区间中每个数加上1。否则什么都不做。这样一来，最后我们只需要看一下询问的区间的区间和是否大于$K$即可。 接下来，我们考虑如何把所有询问一起来二分。 同样还是二分一个答案，把所有答案大于mid的询问丢到右边，其余丢到左边即可。 接下来，我们可以显然发现对于右边的区间，所有修改$<=mid…

题面 P3527 [POI2011]MET-Meteors Solution 我是一直奉行坚决不写树状数组只写线段树理论的，直到这题....... 这题是一道整体二分的模板题。 首先，我们考虑只有一个国家的情况。这不SB问题么 我们可以二分一个答案，然后我们用线段树暴力模拟，暴力Check,复杂度$O(mlogn)$。 显然，如果我们每一个国家都这么搞一轮，复杂度达到了惊人的$O(n\cdot m logn)$，这显然是要T飞的。 因此，我们就得请出伟大的整体二分了。整体二分，顾名思义，就是把所有询问一起二分答案。…