Yosupo 的模板站 索引

最近出现了一个 [刷模板的网站](https://judge.yosupo.jp/)，还挺有趣的。它的每一组测试数据都有名称，可以知道是被什么样的数据卡了（大雾）。 做这个网站的题目，要特别注意，索引基本都是从 $0$ 开始的，要注意换算。 ## Sample（入门题） ### [A+B](https://judge.yosupo.jp/problem/aplusb) 就是 A+B。 ### [Many A+B](https://judge.yosupo.jp/problem/many_aplusb) 多组数据 A+B，记得开 `long long`。 ## Data Structure（数据结构） ### [Associative Array](https://judge.yosupo.jp/problem/associative_array) 维护一个下标范围在 $[0,10^{18}]$ 的数组，支持单点修改和单点查询，操作次数 $10^6$。 这里应该要手写哈希表才是正确的复杂度，而且哈希表一定要手写，因为测试数据里有“unordered_map_killer”（哭）。当然由于时限很大，也可以用 `map` 水过去。 ### [Unionfind](https://judge.yosupo.jp/problem/unionfind) 普通并查集，支持连边和查询两点是否连通。 ### [Static Range Sum](https://judge.yosupo.jp/problem/static_range_sum) 静态区间和，给定一个数列多次查询区间和。前缀和即可。 ### [Static RMQ](https://judge.yosupo.jp/problem/staticrmq) 静态 RMQ，数列长度和查询次数不超过 $5\times 10^5$。 这题数据范围小，并没有变态到需要用笛卡尔树和 $\pm1$ RMQ。 ### [Point Add Range Sum](https://judge.yosupo.jp/problem/point_add_range_sum) 单点加区间和，经典树状数组 / 线段树题。 ### [Point Set Range Composite](https://judge.yosupo.jp/problem/point_set_range_composite) 单点修改区间复合？这是什么东西？原来是维护 $n$ 个一次函数，支持单点修改和区间的函数复合。 函数复合支持结合律，因此用线段树维护函数就可以了。 ### [Range Affine Range Sum](https://judge.yosupo.jp/problem/range_affine_range_sum) 区间仿射变换区间求和？这又是什么东西？原来仿射变换指的是对这个区间应用（apply）一个一次函数，也就是区间乘、区间加之类。 因此只需要写一棵线段树，用懒标记维护每个点“扣押”的一次函数即可。值得一提的是，支持区间加法和乘法双操作的题目用这道题的写法也很方便快捷，无需考虑优先级。 ### [Range Chmin Chmax Add Range Sum](https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum) 区间取 $\min$、区间取 $\max$、区间加、区间和？区间取 $\min$ 就是给出区间 $[l,r]$ 和常数 $t$，令 $a_i=\min(a_i,t)\ (i\in [l,r])$。 似乎需要用所谓的“吉司机线段树”，维护最大值和次大值、最小值和次小值。不会写就先不写了（哭）。 ### [Range Kth Smallest](https://judge.yosupo.jp/problem/range_kth_smallest) 静态区间第 $k$ 小，做法很多，在线的有树套树、可持久化线段树或 Trie 等，离线的有莫队、整体二分等。 ### [Vertex Add Path Sum](https://judge.yosupo.jp/problem/vertex_add_path_sum) 树上单点加路径和，可以用 $\pm 1$ dfs 序写。 ### [Vertex Add Subtree Sum](https://judge.yosupo.jp/problem/vertex_add_subtree_sum) 树上单点加子树和，可以直接 dfs 序搞定。 ### [Persistent UnionFind](https://judge.yosupo.jp/problem/persistent_unionfind) 可持久化并查集，不强制在线。 gitree 水过去啦~ ## Graph（图论） ### [Tree Diameter](https://judge.yosupo.jp/problem/tree_diameter) 树的（带权）直径，要求输出这条路径。 两次 dfs 比较方便，但记得 **清空深度数组**（其实只需要清根节点的就好了）。 ### [Shortest Path](https://judge.yosupo.jp/problem/shortest_path) 最短路，要求输出这条路径。 Dijkstra 的时候记录一下前驱就好了。同时可以复习一下 [`push_heap`](https://zh.cppreference.com/w/cpp/algorithm/push_heap) 和 [`pop_heap`](https://zh.cppreference.com/w/cpp/algorithm/pop_heap) 的写法 ### [Lowest Common Ancestor](https://judge.yosupo.jp/problem/lca) LCA，当然有很多种做法，比如复习一下树链剖分。 ### [Strongly Connected Components](https://judge.yosupo.jp/problem/scc) 输出按缩点后的拓扑序输出强连通分量。写 Tarjan 和拓扑排序即可。 ### [Two-Edge-Connected Components](https://judge.yosupo.jp/problem/two_edge_connected_components) 输出边-双连通分量，用 Tarjan 即可。注意，边双的 Tarjan 比较特殊，需要避免“原路返回”；用数组模拟链表实现时可以把走过来的边的编号传进函数，这样就可以方便地判断是否是“原路返回”。 ## Math（数学） ### [Convolution](https://judge.yosupo.jp/problem/convolution_mod) 卷积，就是多项式乘法，模数是 $998244353$。NTT 模板，甚至还有“fft_killer”。 ### [Inv of Formal Power Series](https://judge.yosupo.jp/problem/inv_of_formal_power_series) 多项式求逆，模数是 $998244353$。 ### [Log of Formal Power Series](https://judge.yosupo.jp/problem/log_of_formal_power_series) 多项式对数，模数是 $998244353$。 ## String（字符串） ### [Suffix Array](https://judge.yosupo.jp/problem/suffixarray) 后缀数组。 ### [Number of Substrings](https://judge.yosupo.jp/problem/number_of_substrings) 子串个数计数，除了后缀排序还要会求 `height`。具体可以参考[我的博客](https://www.luogu.com.cn/blog/Sweetlemon/bucket-radix-suffix-sort)和 [OI-Wiki](https://oi-wiki.org/string/sa/#_13)。