定义

给定\(a,b,c,n\)求对应函数的值：

\(f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\)

\(g(a,b,c,n)=\sum_{i=0}^n i\lfloor\frac{ai+b}{c}\rfloor\)

\(h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\)

定义

对于正整数\(n\)，欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目，写作\(\varphi (n)\)。特别的，\(\varphi (1)=1\)。

定义

“维护一个有序数列，有插入、删除、查询第 k 大、查询前驱、后继等操作”，对于这种问题，我们常用到二叉排序树（BST，Binary Sort Tree，也称二叉查找树、二叉搜索树）这种数据结构，而 Treap 就是对它的一种优化

定义

树状数组（Binary Indexed Tree,BIT）是用于解决区间查询，单点修改的一种数据结构。

定义

二分图又称作二部图，是图论中的一种特殊模型。 设\(G=(V,E)\)是一个无向图，如果顶点\(V\)可分割为两个互不相交的子集\((U,V)\)，并且图中的每条边\((i,j)\)所关联的两个顶点\(i\)和\(j\)分别属于这两个不同的顶点集，则称图\(G\)为一个二分图。

一个无向图为二分图的充要条件是没有奇环。

定义

范围最值查询（Range Minimum Query，RMQ）要求回答数组 \(A[1\ldots n]\) 上区间 \([l, r]\) 的最小值或最大值。ST 表是一种用于静态 RMQ 的预处理数据结构。

定义

两个或者两个以上序列的所有共同上升子序列最长的一个，称为最长公共上升子序列(Longest Common Increasing Subsequence)。

定义

两个或者两个以上序列的所有共同子序列最长的一个，称为最长公共子序列(Longest Common Subsequence)。

定义

在一个序列中最长的单调递增的子序列，称为最长上升子序列(Longest Increasing Subsequence)。