CodeforcesLuogu分析一个不要脑子的做法是线段树分治，即以时间为下标将所有物品与询问挂到线段树上，在线段树上递归时维护一个长度为 $4000$ 的 0/1 背包的 DP 数组即可。标解给的是一个奇妙的分块做法，大概是分成 $p$ 块，从每个交界点往左右跑 0/1 背包，然后每个询问一定会包含一个交界点，直接将左右合并即可。代码因为我懒所以只有第一个方法的代码。// =======...
Luogu分析枚举一个答案 $ans$，那么我们相当于要求在删去边权为 $ans$ 的边后图是否存在一棵生成树，即图是否连通。显然可以考虑线段树分治。具体的，建一棵以边权为下标的线段树，对于每条边权为 $w$ 的边将其放到 $[0,w-1]$ 和 $[w+1,10^5]$ 上。然后在线段树上遍历，遍历到一个节点就将它上面挂着的边连上，这样子到叶结点时就连上了所有不包含该边权的边，判断图是否连...
LOJ分析线段树分治板子题？考虑每条边出现的时间都是若干段区间。我们以时间为下标建一棵线段树，然后在每条边出现的区间挂上这条边。然后我们把询问挂在叶节点上。DFS 这棵线段树，每次到一个节点后就把这个节点上挂的所有边连上。这样子到叶节点时该时间点所有的边都已经连上了，直接询问是否连通即可。这个过程中用一个可撤销并查集维护连通性即可。代码// =========================...