Yosupo 的模板站 索引

· · 个人记录

最近出现了一个 刷模板的网站，还挺有趣的。它的每一组测试数据都有名称，可以知道是被什么样的数据卡了（大雾）。

做这个网站的题目，要特别注意，索引基本都是从 0 开始的，要注意换算。

Sample（入门题）

A+B

就是 A+B。

Many A+B

多组数据 A+B，记得开 long long。

Data Structure（数据结构）

Associative Array

维护一个下标范围在 [0,10^{18}] 的数组，支持单点修改和单点查询，操作次数 10^6。

这里应该要手写哈希表才是正确的复杂度，而且哈希表一定要手写，因为测试数据里有“unordered_map_killer”（哭）。当然由于时限很大，也可以用 map 水过去。

Unionfind

普通并查集，支持连边和查询两点是否连通。

Static Range Sum

静态区间和，给定一个数列多次查询区间和。前缀和即可。

Static RMQ

静态 RMQ，数列长度和查询次数不超过 5\times 10^5。

这题数据范围小，并没有变态到需要用笛卡尔树和 \pm1 RMQ。

Point Add Range Sum

单点加区间和，经典树状数组 / 线段树题。

Point Set Range Composite

单点修改区间复合？这是什么东西？原来是维护 n 个一次函数，支持单点修改和区间的函数复合。

函数复合支持结合律，因此用线段树维护函数就可以了。

Range Affine Range Sum

区间仿射变换区间求和？这又是什么东西？原来仿射变换指的是对这个区间应用（apply）一个一次函数，也就是区间乘、区间加之类。

因此只需要写一棵线段树，用懒标记维护每个点“扣押”的一次函数即可。值得一提的是，支持区间加法和乘法双操作的题目用这道题的写法也很方便快捷，无需考虑优先级。

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

静态区间第 k 小，做法很多，在线的有树套树、可持久化线段树或 Trie 等，离线的有莫队、整体二分等。

Vertex Add Path Sum

树上单点加路径和，可以用 \pm 1 dfs 序写。

Vertex Add Subtree Sum

树上单点加子树和，可以直接 dfs 序搞定。

Persistent UnionFind

可持久化并查集，不强制在线。

gitree 水过去啦~

Graph（图论）

Tree Diameter

树的（带权）直径，要求输出这条路径。

两次 dfs 比较方便，但记得 清空深度数组（其实只需要清根节点的就好了）。

Shortest Path

最短路，要求输出这条路径。

Dijkstra 的时候记录一下前驱就好了。同时可以复习一下 push_heap 和 pop_heap 的写法

Lowest Common Ancestor

LCA，当然有很多种做法，比如复习一下树链剖分。

Strongly Connected Components

输出按缩点后的拓扑序输出强连通分量。写 Tarjan 和拓扑排序即可。

Two-Edge-Connected Components

输出边-双连通分量，用 Tarjan 即可。注意，边双的 Tarjan 比较特殊，需要避免“原路返回”；用数组模拟链表实现时可以把走过来的边的编号传进函数，这样就可以方便地判断是否是“原路返回”。

Math（数学）

Convolution

卷积，就是多项式乘法，模数是 998244353。NTT 模板，甚至还有“fft_killer”。

Inv of Formal Power Series

多项式求逆，模数是 998244353。

Log of Formal Power Series

多项式对数，模数是 998244353。

String（字符串）

Suffix Array

后缀数组。

Number of Substrings

子串个数计数，除了后缀排序还要会求 height。具体可以参考我的博客和 OI-Wiki。