题面 P3810 【模板】三维偏序（陌上花开） Solution 这是一道CDQ分治的模板题。 题目要我们求的是$(a,b,c)$这样的三维“顺序对”的数量。 考虑我们把所有的数按照以$a$为第一关键字，以$b$为第二关键字，以$c$为第三关键字来排序。 这样子，我们就可以保证有可能与某个数形成“顺序对”的数一定在它的左边。 我们都知道，归并排序能用来求逆序对的数量，在这里，也能用类似的方...

题面 4025: 二分图 Solution 这种每条边出现在一段区间的题，我们可以先考虑使用线段树分治来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，我们考虑如何维护一个图是否为二分图的问题。我们知道，一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶...

题面 P4246 [SHOI2008]堵塞的交通 Solution 这题的确是有线段树上大分类讨论的在线做法，但是本菜鸡还是想主要讲一下离线暴力做法。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集...

题面 P5227 [AHOI2013]连通图 Solution 这题可以离线，因此我们可以考虑用线段树分治维护动态图连通性来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间...

题面 #121. 「离线可过」动态图连通性 Solution 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一...

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

题面 4320: ShangHai2006 Homework Solution 这是一道分块妙题。 首先，我们发现这题是对一个比较大的任意模数取模，那我们传统的log数据结构可能还真没法下手。 既然如此，我们考虑分块。 我们把原题中的询问分为两类： 1. $p>=\sqrt{300000}$ 2. $p<\sqrt{300000}$ 对于第二种情况，我们可以开一个桶$f[x]$...

题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题，我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法：对于每只doge，我们都暴力地去建它连向它能跳到的点的边，边权为跳的次数。然后直接求一遍单元最短路即可。 很显然，这玩意的边的数量是$O(n^2)$的，求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的，但是我们会从中...

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

题面 洛谷团队题（尚未入团的请尽快加入团队） 梗 $\huge μ’sic\ Forever!$ 114514.avi.zip 1919810 （(懂的人自然懂(确信)) 真寻酱实在是太可爱了 ⑨个样例(我够良心吧) 真*Solution 稍有常识的人都可以看出,一个文件目录在任意时刻都是一个树的形式（如果没有快捷方式的话）。 像这样：（样例） 解法一 我们来看看type=1啥意思… ...