题面 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飞的。 因此，我们就得请出伟大的整体二分了。整体二分，顾名思义，就是把所有询问一起二分答案。…
题面 P3810 【模板】三维偏序（陌上花开） Solution 这是一道CDQ分治的模板题。 题目要我们求的是$(a,b,c)$这样的三维“顺序对”的数量。 考虑我们把所有的数按照以$a$为第一关键字，以$b$为第二关键字，以$c$为第三关键字来排序。 这样子，我们就可以保证有可能与某个数形成“顺序对”的数一定在它的左边。 我们都知道，归并排序能用来求逆序对的数量，在这里，也能用类似的方法来求“顺序对”的数量。 接下来我们考虑对这个排好序的序列做以$b$为关键字的类似于归并排序的操作。 这里我们要排序的是$[1,…
题面 4025: 二分图 Solution 这种每条边出现在一段区间的题，我们可以先考虑使用线段树分治来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，我们考虑如何维护一个图是否为二分图的问题。我们知道，一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶数。 知道这一点之后，我们考虑用并查集处理这个问题。对于没有环的时候，我们直接连上就好。对于有环的时候，我们就需要知道这两个点的…
题面 P4246 [SHOI2008]堵塞的交通 Solution 这题的确是有线段树上大分类讨论的在线做法，但是本菜鸡还是想主要讲一下离线暴力做法。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一个叶子节点的时候，这个叶子节点代表的询…
题面 P5227 [AHOI2013]连通图 Solution 这题可以离线，因此我们可以考虑用线段树分治维护动态图连通性来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一个叶子节点的时候，这个叶子节点代表的询问上所要连的边一定已经…
题面 #121. 「离线可过」动态图连通性 Solution 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一个叶子节点的时候，这个叶子节点代表的询问上所要连的边一定已经全部连上了，直接在并查集中查询即可。 因为我们这里有撤销（回溯）操作…
题面 3744: Gty的妹子序列 Solution 这是一道分块妙题。 区间逆序对......log数据结构应该是没法搞的。 因此，我们考虑用分块解决这个问题。 设$f[i][j]$表示第$i$块与第$j$块的所有元素的逆序对个数 这个东西我们可以考虑用线段树/树状数组直接搞，我们把所有数字从大到小插入，(数字相同的时候一起插入),每插入一种数字，我们可以直接计算它到其他所有块会新产生的逆序对数：即那个块的大小-已经填好的数字的个数。 上面的东西可以$O(n\cdot \sqrt n \cdot logn)$预处…
题面 4320: ShangHai2006 Homework Solution 这是一道分块妙题。 首先，我们发现这题是对一个比较大的任意模数取模，那我们传统的log数据结构可能还真没法下手。 既然如此，我们考虑分块。 我们把原题中的询问分为两类： 1. $p>=\sqrt{300000}$ 2. $p<\sqrt{300000}$ 对于第二种情况，我们可以开一个桶$f[x]$表示目前为止所有数字%$x$后取得的最小值。这个东西我们在插入数字的时候暴力更新一下即可。 对于第一种情况，事情有点复杂，我们这样做：…
