数据结构/大模拟题记

Tom17 · 2025-11-12 19:13:45 · 个人记录

1. 如何写大模拟

摘自 P13065 [GCJ 2020 #2] Emacs++ 的 提交记录。

出现问题：

1. calc 函数中将oval[x][0/1] 和 oval[y][0/1] 写作 oval[u][0/1] 和 oval[v][0/1]

   • 误将下标写作 id。

2. dfs2 中将右值 oval[cu][0] 写作 oval[cu][1]， oval[cu][1] 写作 oval[cu][0]。

   • 属于理解不好，也可能是笔误。

3. calc 函数中返回值 LL 写作 int。

   • 建议再检查一次。

代码注释：

1. 代码中将每个匹配括号重新标号，id 表示某对括号的 id
2. 相当于从该点出发的边权，且该点位于 l/r 侧，如果填指向侧不那么明了
3. pla[id][2]$ 表示对应 $id$ 的左右括号的位置，$gid$ 表示对应位置括号的 $id
4. 用于查询时的偏序判断
6. - 下标 $[id][0/1]$ 表示记录的是 $id$ 的左括号/右括号到某个位置（或者某个位置 到 $id$ 的左括号/右括号） 的信息 - 下面称该位置为 $pla
7. 在 `dfs3` 中，直接将其信息和走父亲方向的信息 打包给 对应的 $k$ 级父亲的信息数组 所以 $odl/odr/pdl/pdr$ 不包含往父亲方向的信息
8. calc 函数中：
9. 将 0 号点当作虚点，并将第一层的括号串在一起，但是不允许跨过 0 号点，所以将其跨越边权设为 0。

启示：

1. 要把所有信息记在主元的位置
   • 就是说有一种方法是将信息记录在 某个 cu 的第 k 个儿子的 vector<int>[cu][k] 上。
   • 但是这样每次查询的时候就会要先查 id 再转为 rnk 查询，并且有溢出的风险。
   • 对于这种树上问题，一般直接将信息记录在儿子处
   • 并且以儿子的信息（不同点）作为数组的下标，将指向的信息设为名称
   • 这样会比较清晰
2. 合理使用 std::array 可以将数组整体转移 并且一般 std::array 的溢出是 0，vector 溢出后值比较大
3. 合理使用 lambda 函数，记得一般要 [&]

2. B3594. 【NOIP模拟】美食 / P12730 [KOI 2021 Round 2] 美食推荐

本题第一次提交代码的算法考虑树形 DP，要点是：状态记录当前是 cu 子树，只考虑 cu 子树内的贡献，且 cu 子树内的已选点所延伸的最小深度（可能为负），合并形如一个下标第二维：深度取 \min，限制条件；合并的两个深度之和大于当前点深度（需要考虑一个点延伸到另一个子树的情况）。朴素做法视实现是 O(n^2)\sim O(n^3) 的。考虑用线段树记录第二位，然后启发式合并，线段树本质不同状态数是 O(m) 的，时间是 O(m\log m)。

这里主要复习一下线段树的多标记合并。

然后还有序列单调性对线段树的操作优化。

还有一些大模拟的习惯。

1. 线段树多标记合并 (max)。

我们考虑这样的结构：区间加，区间取 \max，区间最大值。

显然维护加标记和取 \max 标记。

取 \max 标记对加标记没有影响，而加标记对取 \max 标记有加的影响，这个不能忘记。

这里没有查区间和，不需要吉司机线段树，只有说区间取 \max 或 \min 操作，同时需要区间加的时候才需要吉司机。吉司机注意势能即可，记录一个最大值/次大值即可。

2. 序列单调性对线段树的操作优化

注意到树形 DP 写法要对序列取一个“向前 \max”操作，即对于每个元素 arr_i 其要对 j>i 的元素 arr_j，使得 arr_i\leftarrow \max \{arr_i,arr_j\}。

考虑上面几个操作如何优化。

首先区间 \max 可以变为单点 \max。但发现这样修改实现的就会比较多，所以可以考虑对修改分析。

发现 “向前取 \max” 这个操作可以变为查询单点改，然后查询后缀查。

我们注意到说区间 \max 这个操作本质上就是右端点取 \max，然后向前取 \max。然后向前取 \max 就变为查询时再往后查询。所以这一部分就可以变为单点取 \max。

区间加是简单的。

所以就不用写两个标记和 down 函数一大堆的下传了。

当有两个区间修改操作时，若存在某些性质，那么我们需要思考能否通过某些性质，使得其中一个的区间修改操作变为单点修改操作。以减少代码长度。

3. 大模拟的习惯

• 写对拍，争取是通过对拍拍出来的问题，这样子在考场上才能调试出来。

• 验证内置数据结构的问题：还是对拍，考虑你的线段树或者其他的什么数据结构，本身自己有没有什么问题。也要通过对拍来写。

• 先写暴力，验证暴力的正确性后，再通过暴力来撰写正解。（这里的暴力不是纯粹的暴力，而是把正解中要用数据结构的转移先用暴力写一次，保证暴力没有问题再写正解，这样不会出现正解写到最后发现其实是伪解的情况。）

• 多用 debug 和 cerr，这个可能才是拍出来问题后最直接的调试方法。瞪眼是瞪不出来的。

• 总结问题：考虑每次写完大模拟/数据结构后总结问题，写在 数据结构/大模拟易错提醒 中，不时复习。

4. 如何建多个图/多棵树？

• CodeChef: Maximum and Minimum / B3834 【CODECHEF】最大值和最小值Maximum and Minimum

简单说一下思路，首先转 MST，然后建 Kruskal 重构树。此时每对点的贡献为其在两个树分别的 LCA 权值的乘积。枚举第一棵树，统计某个点为根的子树内，左儿子和右儿子之间的贡献。LCA 转为差分，变为链加链和。考虑每个点开一个动态开点线段树，然后将第二棵树的树链信息存在线段树内。然后 DFS，每次继承大儿子的贡献，然后用小儿子来查询大儿子，然后把小儿子的每个点（只加原图点对应的点）加入大儿子中。继承大儿子的线段树。小常数 O(n\log^3 n)。

但这里不是讲这个。讲如何处理两个树，以及两个树之间的操作。

首先写成 struct 的形式，然后将函数放在里面。就可以一式两份。

那如何共用信息呢？可以这样，将需要另一个树的信息时，将获取函数挂在参数列表中，然后在主函数中传入对应的 lambda 表达式。

struct tree 
{
    void dfs3(int cu,const function<vector<pii>(int)>& F1) {//得到 T2 的树链剖分信息
        int rnow;
        auto res=F1(rnow);
        for(auto o: res) ...
    }
}T1,T2;

void solve() {

    T1.dfs3(T1.rt, 
        [&](int x) {
            ...
        }
    );
}

记得传引用！！！

就可以在函数内部调用外面的函数了。

5. 调试信息

除了

#define debug cerr<<"now is:"<<__FUNCTION__<<" on line "<<__LINE__<<'\n'

还有

template<typename T> void _fpr(T v){cerr<<v<<'\n';} 
template<typename T,typename... Args> void _fpr(T v,Args... args){cerr<<v<<' ';_fpr(args...);} 
#define fpr(...) cerr<<"[on line "<<__LINE__<<"] ",_fpr(__VA_ARGS__); 

可以更方便地调试。

全家桶：

template<typename T> void _fpr(T v){cerr<<v<<'\n';} 
template<typename T,typename... Args> void _fpr(T v,Args... args){cerr<<v<<' ';_fpr(args...);} 
#define fpr(...) cerr<<"[on line "<<__LINE__<<"] ",_fpr(__VA_ARGS__); 

template<typename T> void _fprl(T v){cerr<<v;} 
template<typename T,typename... Args> void _fprl(T v,Args... args){cerr<<v<<' ';_fprl(args...);} 
#define fprl(...) cerr<<"[on line "<<__LINE__<<"] ",_fprl(__VA_ARGS__); 

template<typename T> void _fprs(T v){cerr<<v<<' ';} 
template<typename T,typename... Args> void _fprs(T v,Args... args){cerr<<v<<' ';_fprs(args...);} 
#define fprs(...) cerr<<"[on line "<<__LINE__<<"] ",_fprs(__VA_ARGS__);