题面 3744: Gty的妹子序列 Solution 这是一道分块妙题。 区间逆序对…log数据结构应该是没法搞的。 因此，我们考虑用分块解决这个问题。 设$f[i][j]$表示第$i$块与第$j$块的所有元素的逆序对个数 这个东西我们可以考虑用线段树/树状数组直接搞，我们把所有数字从大到小插入，(数字相同的时候一起插入),每插入一种数字，我们可以直接计算它到其他所有块会新产生的逆序对数：...

题面 洛谷P3567 Solution 大水题啊，真没什么好讲的 我们考虑建一颗权值主席树，从左往右逐个插入。因为个数满足可减性，因此我们可以很方便的“扣”出$[L,R]$区间构成的主席树。接下来只需要在树上二分看一下有没有出现次数超过$K$的即可。 时间复杂度$O(nlogn)$ 就酱，这题就被我们切掉啦︿(￣︶￣)︿ Solution 123456789101112131415161...

题面 洛谷P3302 Solution 拿到这道题，我们不妨先想一下静态的树上K大怎么搞。 静态树上K大有两种办法，一是树链剖分+平衡树，二是主席树做链前缀和。前者的复杂度是$O(log^2n)$的，而后者只有$O(logn)$。 我们考虑把数字全部离散化，然后开权值主席树，每颗主席树记录从它出发到根的路上每个数字出现了多少个。接下来，我们只需要找到LCA。因为数字出现个数满足可减性，因此...

题面： 传送门：Codeforces 题目大意：给你一颗有根树，点有权值，问你每个节点的子树中距离其不超过k的点的权值的最小值。（边权均为1，强制在线） Solution 这题很有意思。 我们一般看到这种距离不超过k的题目，第一反应一般是建以深度为下标，以dfs序为时间轴的的主席树。 很不幸，区间最小值并不能通过减去历史状态得出某个子树的状态。 所以说，这题妙在思想的转换。 考虑以dfs序...

题面 传送门：洛谷 Solution 你们搞的这道题啊，excited！ . 这题真的很有意思。 首先，我们可以先理解一下题面：固定一个a，找到一个b，c就是a与b的公共子树中的某个点。 那么，我们显然可以把这个b分成两类，第一种是在a上面的，第二种在a下面的。 对于b在a上面的情况，**显然，c一定是a的子树中的某个点，**答案即为$min(K，depth[a])*size[a]$ 对于...