题面 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$后取得的最小值。这个东西我们在插入数字的时候暴力更新一下即可。 对于第一种情况，事情有点复杂，我们这样做：…

题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题，我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法：对于每只doge，我们都暴力地去建它连向它能跳到的点的边，边权为跳的次数。然后直接求一遍单元最短路即可。 很显然，这玩意的边的数量是$O(n^2)$的，求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的，但是我们会从中发现一个问题：既然一个doge的跳跃是多步的，那我们能否直接把几步拆开来，然后省略重复的边？ 例如： 优化为： 这样做看起来很星…

题面 P3247 [HNOI2016]最小公倍数 Solution 这是一道妙题。 首先，根据常识，题面要我们求的是找一条从s,t的路径，使得路径上$max\ a=a,max\ b=b$。 这咋求呢？我们会发现，我们要求的路径本质上是一个连通块，连通块可以考虑用并查集处理。 接下来考虑对a分块，先把所有的边按照$a$来排序，再分块，每个块里连的所有边保证$<=a_{[size*x]}$，如下图所示： 接下来，我们考虑把所有询问按照b从小到大排序去一个个计算，每计算一个询问之前，把$b<=q[i].b$的…

题面 洛咕 Solution 题目要求求出区间众数，强制在线。 区间众数是一个比较尴尬的问题，我们无法用区间数据结构来处理这个问题，因为我们没法很好的合并区间众数的答案。 既然区间数据结构解决不了这个问题，我们可以考虑一下使用基于分块的算法，例如莫队。 这题用莫队非常好处理，不幸的是，这题要求强制在线。 因此我们考虑使用分块算法。 分块算法的核心在于把一整个块的信息压缩起来以便快速处理。 我们要查询一段区间的众数，我们可以考虑这样搞：对于这个区间内连续的块，我们先快速地查询这个连续的块中的众数，然后我们暴力处理这个…