常用的数据结构和算法，主要是ACM中常见算法

算法基础

一、枚举

1.1、两数之和

template <typename type>
std::vector<std::pair<type, type>> target_sum_pairs(const std::vector<type>& arr, type target)
{
    std::vector<std::pair<type, type>> res;
    int len = arr.size();
    // 如果数据很大
    for (int i = 0; i < len - 1; ++i)
        for (int j = i + 1; j < len; ++j)
            if (arr[i] + arr[j] == target)
                res.push_back(std::make_pair(arr[i], arr[j]));
    return res;
    // 如果数据不是特别大，用空间换时间，使用桶来记录遍历过的数
    std::bitset<UINT16_MAX> met(0);
    for (int i = 0; i < len; ++i) {
        if (met[INT16_MAX - arr[i]] == 1)
            res.push_back(std::make_pair(arr[i], -arr[i]));
        met.set(INT16_MAX + arr[i]);
    }
    return res;
}

二、递归分治

2.1、归并排序

template <typename Iter>
void merge_sort_recursion(Iter begin, Iter end)
{
    if (end - begin <= 1) return;
    Iter mid = begin + ((end - begin) >> 1);
    merge_sort_recursion(begin, mid);
    merge_sort_recursion(mid, end);
    std::inplace_merge(begin, mid, end);
}

三、贪心

3.1、知识点

适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
证明
- 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
- 归纳法：先算得出边界情况（例如n=1）的最优解F1，然后再证明：对于每个n，Fn+1都可以由Fn推导出结果。
常见题型
- 我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。（离线）
- 我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护。（在线）
解法
- 排序解法：用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值
- 后悔解法：思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复

3.2、一篇题解

// NOIP 2012 国王游戏  60分，100分需要高精（排序解法）
struct uv {
    long long l, r;
    bool operator<(const uv &x) const {
        return std::max(x.r, l*r) < std::max(r, x.l*x.r);
    }
};

void solve_noip2012_kinggame()
{
    int n;
    std::cin >> n;
    std::vector<uv> v(n);
    long long int kl, kr;
    std::cin >> kl >> kr;
    for (int i = 0; i < n ;++i)
        std::cin >> v[i].l >> v[i].r;
    std::sort(v.begin(), v.end());
    long long max_coins = -1;
    for (int i = 0; i < n; ++i) {
        if (kl / v[i].r > max_coins) max_coins = kl / v[i].r;
        kl *= v[i].l;
    }
    std::cout << max_coins << std::endl;
}

// 「USACO09OPEN」工作调度 Work Scheduling（后悔解法）
struct f {
    long long d;
    long long p;
} a[100005];

bool cmp(f A, f B) { return A.d < B.d; }

std::priority_queue<long long, std::vector<long long>, std::greater<long long>> q;

void solve_USACO09OPEN() {
    long long n, i;
    std::cin >> n;
    for (i = 1; i <= n; i++)
        std::cin >> a[i].d >> a[i].p;
    std::sort(a + 1, a + n + 1, cmp);
    long long ans = 0;
    for (i = 1; i <= n; i++) {
        if (a[i].d <= (int)q.size()) {  // 超过截止时间
            if (q.top() < a[i].p) {       // 后悔
                ans += a[i].p - q.top();
                q.pop();
                q.push(a[i].p);
            }
        } else {  // 直接加入队列
            ans += a[i].p;
            q.push(a[i].p);
        }
    }
    std::cout << ans << std::endl;
}

四、排序

4.1、选择排序

// 每次找出第i小的元素
template <typename type>
void select_sort(std::vector<type> &arr)
{
    int size = arr.size();
    for (int i = 0; i < size - 1; ++i) {
        int ith = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[ith])
                ith = j;
        }
        std::swap(arr[ith], arr[i]);
    }
}

4.2、冒泡排序

// 小的数上浮，经过i次排序的最后i项必然是最大的i项
template <typename type>
void bubble_sort(std::vector<type> &arr)
{
    int size = arr.size();
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - 1; ++j) {
            if (arr[j+1] < arr[j])
                std::swap(arr[j+1], arr[j]);
        }
    }
}

4.3、插入排序

// 分为有序区和无序区
template <typename type>
void insert_sort(std::vector<type> &arr)
{
    int size = arr.size();
    for (int i = 1; i < size; ++i) {
        type tmp = arr[i];
        int j = i - 1;
        for ( ; j >= 0 && tmp < arr[j]; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = tmp;
    }
}

4.4、计数排序

// 计算每个数出现了几次
// 求出每个数出现次数的 前缀和
// 利用出现次数的前缀和，从右至左计算每个数的排名
template <typename type>
void counting_sort(std::vector<type> &arr)
{
    type max_val = *(std::max_element(arr.begin(), arr.end()));
    type min_val = *(std::min_element(arr.begin(), arr.end()));
    int size = arr.size();
    std::vector<type> cnt(max_val - min_val + 1, 0);
    std::vector<type> tmp(arr);
    for (int i = 0; i < size; ++i) ++cnt[arr[i] - min_val];
    for (int i = 1; i <= max_val - min_val; ++i) cnt[i] += cnt[i-1];
    for (int i = size - 1; i >= 0; --i) arr[--cnt[tmp[i] - min_val]] = tmp[i];
}

4.5、基数排序

// 将元素拆分为多个关键字，挨个根据关键字排序
template <typename type>
void radix_sort(std::vector<type> &arr)
{
    size_t size = arr.size();
    std::vector<type> cnt(10, 0);
    std::vector<type> tmp(size, 0);
    type max_val = *(std::max_element(arr.begin(), arr.end()));
    type min_val = *(std::min_element(arr.begin(), arr.end()));
    int max_digits = 0;
    while (max_val) {
        ++max_digits;
        max_val /= 10;
    }
    int base = 1;

    for (int k = 0; k < max_digits; ++k) {
        std::fill(cnt.begin(), cnt.end(), 0);
        for (int i = 0; i < size; ++i)
            ++cnt[((arr[i] - min_val) / base) % 10];

        for (int i = 0, t = 0; i < 10; ++i)
            for (int j = 0; j < size; ++j)
                if (((arr[j] - min_val) / base) % 10 == i)
                    tmp[t++] = arr[j];
        for (int i = 0; i < size; ++i)
            arr[i] = tmp[i];
        base *= 10;
    }
}

4.6、快速排序

// 将数列划分为两部分（要求保证相对大小关系）
// 递归到两个子序列中分别进行快速排序
// 不用合并，因为此时数列已经完全有序
template <typename type>
void quick_sort_solve(std::vector<type> &arr, int32_t l, int32_t r)
{
    if (l > r) return;
    type base = arr[l], left = l, right = r;
    while (left < right) {
        while (arr[right] > base && left < right)
            right--;
        if (left < right) {
            arr[left] = arr[right];
            left++;
        }
        while (arr[left] < base && left < right)
            left++;
        if (left < right) {
            arr[right] = arr[left];
            right--;
        }
    }
    arr[left] = base;
    quick_sort_solve(arr, l, left-1);
    quick_sort_solve(arr, left+1, r);
}

template <typename type>
void quick_sort(std::vector<type> &arr, int32_t l, int32_t r)
{
    std::random_device rd;
    std::mt19937 g(rd());

    std::shuffle(arr.begin(), arr.end(), g);
    quick_sort_solve<type>(arr, l, r);
}

// 三路快速排序在处理含有多个重复值的数组时，效率远高于原始快速排序。其最佳时间复杂度为O(n)
template <typename type>
void quick_sort(type arr[], const int len)
{
    if (len <= 1) return;
    const type pivot = arr[rand() % len];
    int i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i] < pivot)
            std::swap(arr[i++], arr[j++]);
        else if (pivot < arr[i])
            std::swap(arr[i], arr[--k]);
        else
            i++;
    }
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}

// 寻找第K大的数（线性）
// 模板的 type 参数表示元素的类型，此类型需要定义小于（<）运算
template <typename type>
// arr 为查找范围数组，rk 为需要查找的排名（从 0 开始），len 为数组长度
type find_kth_element(type arr[], int rk, const int len) {
    if (len <= 1) return arr[0];
    // 随机选择基准（pivot）
    const type pivot = arr[rand() % len];
    // i：当前操作的元素
    // j：第一个等于 pivot 的元素
    // k：第一个大于 pivot 的元素
    int i = 0, j = 0, k = len;
    // 完成一趟三路快排，将序列分为：
    // 小于 pivot 的元素 ｜ 等于 pivot 的元素 ｜ 大于 pivot 的元素
    while (i < k) {
        if (arr[i] < pivot)
            std::swap(arr[i++], arr[j++]);
        else if (pivot < arr[i])
            std::swap(arr[i], arr[--k]);
        else
            i++;
    }
    // 根据要找的排名与两条分界线的位置，去不同的区间递归查找第 k 大的数
    // 如果小于 pivot 的元素个数比k多，则第 k 大的元素一定是一个小于 pivot 的元素
    if (rk < j) return find_kth_element(arr, rk, j);
        // 否则，如果小于 pivot 和等于 pivot 的元素加起来也没有 k 多，
        // 则第 k 大的元素一定是一个大于 pivot 的元素
    else if (rk >= k)
        return find_kth_element(arr + k, rk - k, len - k);
    // 否则，pivot 就是第 k 大的元素
    return pivot;
}

4.7、归并排序

// 基于分治，将数组分段排序后合并
template <typename Iter>
void merge_sort(Iter begin, Iter end)
{
    if (end - begin <= 1) return;
    Iter mid = begin + ((end - begin) >> 1);
    merge_sort(begin, mid);
    merge_sort(mid, end);
    std::inplace_merge(begin, mid, end);
}

// array version
int tmp[100], a[100];
void merge(int l, int r) {
    if (r - l <= 1) return;
    int mid = l + ((r - l) >> 1);
    merge(l, mid), merge(mid, r);
    for (int i = l, j = mid, k = l; k < r; ++k) {
        if (j == r || (i < mid && a[i] <= a[j]))
            tmp[k] = a[i++];
        else
            tmp[k] = a[j++];
    }
    for (int i = l; i < r; ++i) a[i] = tmp[i];
}

4.8、堆排序

// 建立在堆上的选择排序
template <typename type>
void heap_sort(std::vector<type> &arr, int size)
{
    for (int i = (size - 2) / 2; i >= 0; --i) sift_down(arr, i, size - 1);
    for (int i = size - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        sift_down(arr, 0, i - 1);
    }
}

template <typename type>
void sift_down(std::vector<type> &arr, int start, int end)
{
    int parent = start;
    int child = parent * 2 + 1;
    while (child <= end) {
        // 先比较两个子结点大小，选择最大的
        if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
        // 如果父结点比子结点大，代表调整完毕，直接跳出函数
        if (arr[parent] >= arr[child])
            return;
        else {  // 否则交换父子内容，子结点再和孙结点比较
            std::swap(arr[parent], arr[child]);
            parent = child;
            child = parent * 2 + 1;
        }
    }
}

4.9、桶排序

// 设置一个定量的数组当作空桶
// 遍历序列，并将元素一个个放到对应的桶中
// 对每个不是空的桶进行排序
// 从不是空的桶里把元素再放回原来的序列中
template <typename type>
void bucket_sort(std::vector<type> &arr)
{
    type max_val = *std::max_element(arr.begin(), arr.end());
    type min_val = *std::min_element(arr.begin(), arr.end());
    const int block_nums = (1 << 10);
    auto bucket_size = (max_val - min_val) / block_nums + 1;
    std::vector<std::vector<type>> bucket(bucket_size);
    for (auto elem: arr)
        bucket[(elem - min_val) / block_nums].push_back(elem);
    int t = 0;
    for (auto &block: bucket) {
        insert_sort(block);
        for (auto elem: block)
            arr[t++] = elem;
    }
}

template <typename type>
void insert_sort(std::vector<type> &arr)
{
    int size = arr.size();
    for (int i = 1; i < size; ++i) {
        type tmp = arr[i];
        int j = i - 1;
        for ( ; j >= 0 && tmp < arr[j]; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = tmp;
    }
}

4.10、希尔排序

// 缩小增量排序（插入排序的优化版本）
// 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
// 对这些子序列进行插入排序
// 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1
template <typename type>
void shell_sort(std::vector<type> &arr)
{
    size_t length = arr.size();
    int h = 1;
    while (h < length / 3)
        h = 3 * h + 1;
    while (h >= 1) {
        for (int i = h; i < length; i++)
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h)
                std::swap(arr[j], arr[j - h]);
        h = h / 3;
    }
}

一、二分

1.1、左闭右开

// [left ,mid) [mid+1, right)
template <typename type>
bool binary_search(std::vector<type> v, type n) {
    uint32_t left = 0, right = v.size(), mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (n == v[mid]) return true;
        else if (n < v[mid]) right = mid;
        else left = mid + 1;
    }
    return false;
}

template <typename type>
std::pair<bool, typename std::vector<type>::const_iterator>
        binary_search(const std::vector<type>& arr, type x)
{
    auto left = arr.begin(), right = arr.end();
    auto mid = arr.begin() + type(arr.size() / 2);
    while (left < right) {
        if (*mid == x)
            return std::make_pair(true, mid);
        else if (*mid < x)
            left = mid + 1;
        else
            right = mid;
        mid = left + (right - left) / 2;
    }
    return std::make_pair(false, arr.end());
}

template <typename type>
std::pair<bool, typename std::vector<type>::const_iterator>
        binary_search(const std::vector<type>& arr, type x)
{
    auto second = std::lower_bound(arr.begin(), arr.end(), x);
    if (second != arr.end())
        return make_pair(true, second);
    else
        return make_pair(false, second);
}

1.2、左闭右闭

// [left, mid] [mid + 1, right]
while (left <= right) {
    mid = (left + right) / 2;
    if (n == v[mid]) return true;
    else if (n < v[mid]) right = mid - 1;
    else left = mid + 1;
}

二、差分&前缀和

2.1、差分数组

// 区间左加，区间右减
for (int i = 1; i <= m; ++i)    {
    Diff[L[i]] += D[i];
    Diff[R[i] + 1] -= D[i];
}

2.2、前缀和数组

for (int i = 1; i <= n; ++i)    {
    S[i] = S[i-1] + Diff[i];
}

数论

一、欧基里德及扩展

1.1、GCD

// gcd
long long gcd(long long a, long long b) {return b ? gcd(b, a%b) : a;}
long long gcd(long long a, long long b) {while (b^=a^=b^=a%=b); return a;}
long long gcd(long long a, long long b)    {
    long long r;
    while (b) {r = b; b = a % b; a = r;}z
    return a;
}
// lcm
long long lcm(long long a, long long b) {return a * b / gcd(a, b);}

1.2、Extend_GCD

// 求解ax+by=gcd(a,b)的解 (x,y)
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (a==0&&b==0) return -1;
    if (b==0) {x=1; y=0; return a;}
    long long d = extend_gcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}

// 求逆元
long long inv(long long a, long long n) {
    long long x, y;
    long long d = extend_gcd(a, n, x, y);
    if (d==1) return (x%n+n)%n;
    else return -1;
}

// 求解同余方程
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
	if (b){
		long long r = extend_gcd(b, a%b, y, x);
		y -= x*(a/b); return r;
	} else { x=1; y=0; return a; }
}
long long solve(long long a, long long b, long long mod) {
	long long x, y, r = extend_gcd(a, mod, x, y);
	if (b%r) return -1; else x = (x+mod)%mod*b/r;
	// return x; 这个是返回通解
	return x%(mod/r); //返回最小解
} 

二、同余

2.1、相关概念

a=b (mod m) 同余;
a|b a能整除b,a是b的因子;
a*x=1 (mod p); x = inv(a) (mod p); 	// 逆元
a/b (mod p) <=> (inv(b)*a)%p; 	  	// 分数取模
a/b (mod p) <=> b*c=a (mod p);		// 化解为求同余方程

// 同余
(a+b)%c = (a%c + b%c)%c;
(a-b)%c = (a%c - b%c + c)%c;
(a*b)%c = (a%c*b%c)%c;
(a/b)%c = (a*inv(b))%c;

2.2、逆元

// 扩欧
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
	if (b){
		long long r = extend_gcd(b, a%b, y, x);
		y -= x*(a/b); return r;
	} else { x=1; y=0; return a; }
}

long long inv(long long a, long long n) {
    long long x, y;
    long long d = extend_gcd(a, n, x, y);
    if (d==1) return (x%n+n)%n;
    else return -1;
}

// 简洁写法（只能求解a<m的情况）
long long inv(long long a, long long m) {
    if (a==1) return 1;
    return inv(m%a, m)*(m-m/a)%m;
}

// 欧拉函数（费马小定理）
// mod为素数，且a,m互质
long long pow_mod(long long a, long long b, long long mod)    {
    long res = 1;
    while (b) {
        if (b&1) res = (res * a)%mod;
        b >>= 1; a = (a*a)%mod;
    }
    return res;
}

long long inv(long long a, long long mod) {
    return pow_mod(a, mod-2, mod);
}

// 线性算法（适合求多个元素的逆元）
vector<int> inv(p);
inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

三、素数

3.1、素数分布

/* 小于x的素数个数pi(x)随x增长趋近于x/ln(x) */

/* 对于任意正整数n，至少存在n个连续的正合数 */

3.2、素数猜想

/* 伯兰特猜想： 对于任意给定的正整数n>3，则至少存在一个质数p，符合n < p < 2*n-2
另一个稍弱的说法是：对于任意给定的正整数n>1，存在一个质数p，符合n < p < 2*n */
    
/* 孪生素数猜想： 存在无数多形如p, p+2的素数对 */

/* 歌德巴赫猜想： 每个大于2的正偶数可以写成两个素数的和 */

3.3、素数测试

/* 埃式筛法： 正整数n是素数，当且仅当它不能被任何一个小于sqrt(n)的素数整除 */

/* 6N+1法： 除了2和3以外，所有素数都可以表示为6N+1的形式 */

3.4、算数基本定理

/* 任何大于1的正整数n都可以表示为若干素数之积 */

/* n!的素因子分解中的素数p的幂为[n/p]+[n/p^2]+[n/p^3]+...
令p[n]是第n个素数，其中n是正整数，那么p[n]~nln(n) */

3.5、素数判定

3.5.1、质数筛

// 朴素质数筛
bool simple_prime_sieve(long long n)     {
    if (n <= 1)   return false;
    for (int i = 2; i * i <= n; ++i)     {
        if (n % i == 0) return false;
    }
    return true;
}

// 埃式筛
const long long MAXN = 100010;
long long cnt = 0;		// 素数个数
long long prime[MAXN]; 	// 存素数
bool flag[MAXN];       	// true代表为素数，false代表为合数
void angstrom_sieve(long long n)    {
    memset(flag, true, sizeof(flag));
    for (int i = 2; i <= n; ++i)    {
        if (flag[i]) { prime[cnt++] = i;
            for (long long j = (i << 1); j <= n; j += i) flag[j] = false;
        }
    }
}

// 欧拉筛
const long long MAXN = 100010;
long long prime[MAXN], cnt = 0;
bool vis[MAXN];
void euler_sieve(long long n)    {
    memset(prime, 0, sizeof(prime));
    memset(vis, true, sizeof(vis));
    for (int i = 2; i <= n; ++i)    {
        if (vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && prime[j]*i <= n; ++j)    {
            vis[prime[j] * i] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

3.5.2、Miller素数测试

long long prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
long long qmult(long long a, long long b, long long c) { // 快乘（防止爆long long）
    long long ans = 0, res = a;
    while(b) {
        if(b & 1) ans = (ans + res) % c;
        res = (res + res) % c;
        b >>= 1;
    }
    return ans;
}
long long qpow(long long a, long long b, long long m) { // 快速幂
    long long ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}
bool miller(long long x) {  // 判断素数
    long long s = 0, t = x-1;
    if(x == 2) return true; //2是素数
    if(x < 2 || !(x & 1)) return false;  //如果x是偶数或者是0，1，那它不是素数
    while(!(t & 1)) {s++; t >>= 1;} //将x-1分解成(2^s)*t的样子
    for(long long i = 0; i < 10 && prime[i] < x; i++) { //随便选一个素数进行测试
        long long a = prime[i];
        long long b = qpow(a, t, x);   //先算出a^t
        for(long long j = 1; j <= s; j++) { //然后进行s次平方
            long long k = qmult(b,b,x);  //求b的平方
            if(k == 1 && b != 1 && b != x-1) return false;
            b = k;
        }
        if(b != 1) return false;    //用费马小定理判断
    }
    return true;    //如果进行多次测试都是对的，那么x就很有可能是素数
}

3.5.3、Meissel-Lehmer

const long long N = 9e3;//通过知道前面的n^1/3的质数可以推断后面n^2/3的质数所以可以适当减小
bool np[N];
int prime[N], pi[N];
int getprime() {
    int cnt = 0;
    np[0] = np[1] = true;
    pi[0] = pi[1] = 0;
    for(int i = 2; i < N; ++i) {
        if(!np[i]) prime[++cnt] = i;
        pi[i] = cnt;
        for(int j = 1; j <= cnt && i * prime[j] < N; ++j) {
            np[i * prime[j]] = true;
            if(i % prime[j] == 0)   break;
        }
    }
    return cnt;
}
const int M = 2;//为了减小内存可以不过是质数
const int PM = 2 * 3 * 5 ;//为了减小内存可以不过要按质数减小如去掉17
int phi[PM + 1][M + 1], sz[M + 1];
void init() {
    getprime();
    sz[0] = 1;
    for(int i = 0; i <= PM; ++i)  phi[i][0] = i;
    for(int i = 1; i <= M; ++i) {
        sz[i] = prime[i] * sz[i - 1];
        for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
    }
}
int sqrt2(long long x) {
    long long r = (long long)sqrt(x - 0.1);
    while(r * r <= x)   ++r;
    return int(r - 1);
}
int sqrt3(long long x) {
    long long r = (long long)cbrt(x - 0.1);
    while(r * r * r <= x)   ++r;
    return int(r - 1);
}
long long getphi(long long x, int s) {
    if(s == 0)  return x;
    if(s <= M)  return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
    if(x <= prime[s]*prime[s])   return pi[x] - s + 1;
    if(x <= prime[s]*prime[s]*prime[s] && x < N) {
        int s2x = pi[sqrt2(x)];
        long long ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
        for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
        return ans;
    }
    return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
long long getpi(long long x) {
    if(x < N)   return pi[x];
    long long ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
    for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
    return ans;
}
long long lehmer_pi(long long x) {//小于等于n的素数有多少个
    if(x < N)   return pi[x];
    int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
    int b = (int)lehmer_pi(sqrt2(x));
    int c = (int)lehmer_pi(sqrt3(x));
    long long sum = getphi(x, a) +(long long)(b + a - 2) * (b - a + 1) / 2;
    for (int i = a + 1; i <= b; i++) {
        long long w = x / prime[i];
        sum -= lehmer_pi(w);
        if (i > c) continue;
        long long lim = lehmer_pi(sqrt2(w));
        for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
    }
    return sum;
}

3.6、素因子分解

const long long MAXN = 10000;
long long prime[MAXN+1];
void getPrime() {
    memset(prime, 0, sizeof(prime));
    for (int i=2; i<=MAXN; ++i) {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j=1; j<=prime[0]&&prime[j]<=MAXN/i; ++j) {
            prime[prime[j]*i]=1;
            if (i%prime[j]==0) break;
        }
    }
}
long long factor[100][2];
long long fatCnt;
long long getFactors(long long x) {
    fatCnt = 0;
    long long tmp = x;
    for (int i=1; prime[i]<=tmp/prime[i]; ++i) {
        factor[fatCnt][1] = 0;
        if (tmp%prime[i]==0) {
            factor[fatCnt][0] = prime[i];
            while (tmp%prime[i] == 0) {
                factor[fatCnt][1]++;
                tmp/=prime[i];
            }
            fatCnt++;
        }
    }
    if (tmp!=1) {
        factor[fatCnt][0]=tmp;
        factor[fatCnt++][1]=1;
    }
    return fatCnt;
}

// factor[i][0] 质因子， factor[i][1] 幂次
int main(void) {
    getPrime();
    long long int n; cin >> n;
    long long cnt = getFactors(n);
    for (int i = 0; i < cnt; ++i) cout << factor[i][0] << ' ' << factor[i][1] << '\n';
    return 0;
}

四、积性函数

4.1、定义

// 任意(x,y)=1，有f(xy)=f(x)f(y) 则称f(n)为一个积性函数
// 任意(x,y)，有f(xy)=f(x)f(y) 则称f(n)为完全积性函数

4.2、常见类型

4.2.1、欧拉函数

/* 定义：f(x)表示[1,x]中与x互质数的个数 */

/* 性质 */
gcd(n, m) = 1; f(n*m) = f(n) * f(m);
// 当x为素数时，f(x)=x-1，当x为奇素数时f(2x)=x-1
// 当n为奇数时，f(n)=f(2n)
// n>2，则其欧拉函数值为偶数

4.2.2、莫比乌斯函数

```

### 4.3、性质

```cpp
f(1) = 1;
积性函数的前缀和也是积性函数

五、矩阵和线性方程组

5.1、求解模线性方程组

// 中国剩余定理 (mi, mj) = 1 （互质）
inline long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (a==0&&b==0) return -1;
    if (b==0) {x=1; y=0; return a;}
    long long d = extend_gcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}

long long CRT(long long a[], long long m[], long long k) {
    long long x, y, Mi, ans = 0, M = 1;
    for (int i = 0; i < k; i++) M *= m[i]; 
    for (int i = 0; i < k; i++) {
        Mi = M / m[i];
        long long d = extend_gcd(m[i], Mi, x, y);     // y 为逆元 -- Mi*y === 1 (% m[i])
        ans = (ans + a[i]*y*Mi) % M;
    }
    return (ans>0) ? ans % M : (ans+M);
}

// (mi, mj) ?= 1 （不一定互质）
inline long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (a==0&&b==0) return -1;
    if (b==0) {x=1; y=0; return a;}
    long long d = extend_gcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}

// (mi, mj) ?= 1 （不一定互质）
long long mod(long long a, long long m) {    //处理取模
    long long res = a%m;
    if(res <= 0) res += m;
    return res;
}
long long CRT(long long a[], long long m[], long long k) {
    long long ans = a[0];
    long long lcm = m[0], x, y, d;
    if(ans == 0) ans = m[0];
    for(long long i = 1; i < k; ++i) {
        d = extend_gcd(lcm, m[i], x, y);    //求t: t = (a[i]-ans)/d*x;
        if((a[i]-ans)%d) return 0;
        ans = mod(ans + lcm*mod((a[i]-ans)/d*x, m[i]/d),(lcm/d*m[i]));
        lcm = lcm/d*m[i];
    }
    return ans;
}

5.2、求解线性方程组的解

//  高斯消元法求方程组的解

const long long MAXN = 300;
//  有equ个方程，var个变元。增广矩阵行数为equ，列数为var＋1，分别为0到var
long long equ, var;
long long a[MAXN][MAXN];  //  增广矩阵
long long x[MAXN];        //  解集
long long free_x[MAXN];   //  用来存储自由变元（多解枚举自由变元可以使用）
long long free_num;       //  自由变元的个数

//  返回值为－1表示无解，为0是唯一解，否则返回自由变元个数
int Gauss() {
    long long max_r, col, k;
    free_num = 0;
    for (k = 0, col = 0; k < equ && col < var; k++, col++) {
        max_r = k;
        for (int i = k + 1; i < equ; i++) 
            if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i;
        if (a[max_r][col] == 0) {
            k--;
            free_x[free_num++] = col;   //  这是自由变元
            continue;
        }
        if (max_r != k) 
            for (int j = col; j < var + 1; j++) swap(a[k][j], a[max_r][j]);
        
        for (int i = k + 1; i < equ; i++) 
            if (a[i][col] != 0) 
                for (int j = col; j < var + 1; j++) a[i][j] ^= a[k][j];
    }
    for (int i = k; i < equ; i++) {
        if (a[i][col] != 0) return -1;
    }
    if (k < var) return var - k; //  自由变元个数

    //  唯一解，回代
    for (int i = var - 1; i >= 0; i--) {
        x[i] = a[i][var];
        for (int j = i + 1; j < var; j++) x[i] ^= (a[i][j] && x[j]);
    }
    return 0;
}

六、莫比乌斯

七、阶乘

7.1、斯特林公式

n! = sqrt(2*pi*n)(n/e)^n;

八、三角形数

8.1、定义

/* 三角形数 */
1, 3, 6, 10, 15, 21....
    
/* 正方形数 */
1, 4, 9, 16....

8.2、公式

f(n) = n*(n+1)/2   or  ((2n+1)^2-1)/8

8.3、性质

第n个三角形数是前n个自然数之和
所有大于3的三角形数都不是质数
最开始的n个立方数的和是第n个三角形数的平方
所有三角形数的倒数之和是2
任何三角形乘8再加1是一个平方数
两个公式 n*(2n+1)	n*(2n-1)
任意一个自然数都可以表示为三个三角形数之和

九、降幂公式

十、线性基

10.1、定义

/* 若干数的线性基是一组数a1,a2,a3,...,an,其中ax的最高位的1在第x位 */

10.2、性质

/* 最高位1的位置互不想同 */
/* 线性基的任意一个子集的异或和不为0 */
/* 如果线性及是满的，它的异或集合为[1, x^{n-1}] */
/* 通过线性基中元素xor出的数的值域相同，即线性基可以通过互相xor，能够构出原来的数相互xor构出的所有的数 */
/* 线性基中元素互相异或，异或集合不变 */

10.3、构造方法

对每一个数从高位到低位扫，扫到第x位为1时，若ax不存在，则ax=p并结束次数的扫描，否则令p=p xor ax

10.4、应用

/* 给出一个数组，询问一个数能否表示为数组中的某些数的异或和 */

/* 给出一个数组，询问第k小/最大/最小异或和 */

十一、快速幂

11.1、快速幂

/* 整型快速幂（不带模） */
long long quick_pow(long long a, long long b)    {
    long long res = 1LL;
    while (b) {
        if (b&1) res = res * a;
        b >>= 1; a *= a;
    }
    return res;
}
/* 整型快速幂（带模） */
long long quick_pow(long long a, long long b, long long mod)    {
    long long res = 1LL;
    while (b) {
        if (b&1) res = (res * a) % mod;
        b >>= 1; a = (a * a) % mod;
    }
    return res;
}

11.2、矩阵快速幂

/* 矩阵快速幂（带模） */
const long long N = 110;
struct matrix {
    long long a[N][N];
    matrix(){memset(a, 0, sizeof(a));}
};

matrix multi(matrix a, matrix b, long long mod)    {
    matrix c;
    for (int i = 0; i < n; ++i)    {
        for (int j = 0; j < n; ++j)    {
            for (int k = 0; k < n; ++k)    {
                c.a[i][j] = ((a.a[i][k] * b.a[k][j]) % mod + c.a[i][j]) % mod;
            }
        }
    }
    return c;
}

void quick_pow(matrix& a, long long k, long long mod)    {
    for (int i = 0; i < n; ++i) res.a[i][i] = 1; // 初始化为单位矩阵
    while (k) {
        if (k & 1)    res = multi(res, a, mod);
        k >>= 1; a = multi(a, a, mod);
    }
    return;
}

11.3、多项式快速幂

/* 多项式快速幂 */

/* 快速阶乘 */

数据结构

一、划分树

二、RMQ

三、树链剖分

四、伸展树

五、动态树

六、主席树

七、Trep

八、KD树

九、替罪羊树

十、线段树和树状数组

10.1、树状数组

// 单点操作，单点查询查询
const long long MAXN = 2000010;
long long n, tree[MAXN];
inline long long lowbit(long long x) {return x & (-x);}
void add(long long x, long long k) { // 单点修改元素
    while (x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}
long long sum(long long x) {
    long long ans = 0;
    while(x != 0) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans; // 返回前缀和
}

long long query(long long x) { // 单点查询
    return sum(x)-sum(x-1);
}

// 区间操作，区间查询（自己写的，太慢了）
// 可AC洛谷树状数组模板一（单点操作，区间查询）
const long long MAXN = 2000010;
long long n, tree[MAXN];
inline int lowbit(int x) {return x & (-x);}
void add(int x, long long k) {
    while (x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}
long long sum(int x) {
    long long ans = 0;
    while(x != 0) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

void sec_add(int l, int r, long long v) { // 区间加减元素
    for (int i = l; i <= r; ++i) add(i, v);
}

long long sec_query(int l, int r) { // 区间查询
    return sum(r) - sum(l-1);
}


// 优化（区间操作，区间查询使用此模板）
const int MAXN = 200010;
long long A[MAXN], B[MAXN];
int n, m;
int lowbit (int x) {return x & (-x);}
void modify(int l, int r, long long v) { //维护差分数组 
  ++r;
  for (int i=l; i<=n; i+=lowbit(i))  A[i]+=v, B[i]+=l*v;
  for (int i=r; i<=n; i+=lowbit(i))  A[i]-=v, B[i]-=r*v;
}


long long query(int l, int r) { // 区间查询
  long long res = 0;
  for (int i=r; i; i-=lowbit(i)) res += (r+1)*A[i]-B[i];
  for (int i=l-1; i; i-=lowbit(i)) res -= l*A[i]-B[i];
  return res;
}

10.2、线段树

// 区间修改，单点查询
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
const int MAXN = 500010;
int input[MAXN];
struct node {
    int left,right;
    int num;
}tree[MAXN<<2];

void build(int left,int right,int index) {
    tree[index].num=0;
    tree[index].left=left;
    tree[index].right=right;
    if(left==right) return ;
    int mid=(right+left)/2;
    build(left,mid,index*2);
    build(mid+1,right,index*2+1);
}
void pls(int index,int l,int r,int k) {
    if(tree[index].left>=l && tree[index].right<=r) {
        tree[index].num+=k;
        return ;
    }
    if(tree[index*2].right>=l)
       pls(index*2,l,r,k);
    if(tree[index*2+1].left<=r)
       pls(index*2+1,l,r,k);
}
void search(int index,int dis) {
    ans+=tree[index].num;
    if(tree[index].left==tree[index].right) return ;
    if(dis<=tree[index*2].right) search(index*2,dis);
    if(dis>=tree[index*2+1].left) search(index*2+1,dis);
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    build(1, n, 1);
    for(int i = 1; i <= n; i++) cin >> input[i];
    for(int i = 1; i <= m; i++) {
        int op; cin >> op;
        if(op ==1 ) {
            int l, r, v; cin >> l >> r >> v;
            pls(1, l, r, v);
        }
        else {
            ans = 0;
            int x; cin >> x;
            search(1, x);
            cout << ans + input[x] << '\n';
        }
    }
    return 0;
}

// 区间修改，区间查询
#include <bits/stdc++.h>
using namespace std;
long long n,m;
const int MAXN = 1000010;
struct node {
    long long l,r,data;
    long long lt;    
}tree[MAXN<<2];
long long arr[MAXN];
void build(long long l, long long r, long long index, long long arr[]) {
    tree[index].lt=0;
    tree[index].l=l;
    tree[index].r=r;
    if(l == r) {
        tree[index].data=arr[l];
        return ;
    }
    long long mid=(l+r)/2;
    build(l,mid,index*2,arr);
    build(mid+1,r,index*2+1,arr);
    tree[index].data=tree[index*2].data+tree[index*2+1].data;
    return ;
}
void push_down(long long index) {
    if(tree[index].lt != 0) {
        tree[index*2].lt+=tree[index].lt;
        tree[index*2+1].lt+=tree[index].lt;
        long long mid=(tree[index].l+tree[index].r)/2;
        tree[index*2].data+=tree[index].lt*(mid-tree[index*2].l+1);
        tree[index*2+1].data+=tree[index].lt*(tree[index*2+1].r-mid);
        tree[index].lt=0;
    }
    return ;
}
void update(long long index, long long l, long long r, long long k) {
    if(tree[index].r <= r && tree[index].l >= l) {
        tree[index].data += k*(tree[index].r-tree[index].l+1);
        tree[index].lt += k;
        return ;
    }
    push_down(index);
    if(tree[index*2].r>=l)
        update(index*2,l,r,k);
    if(tree[index*2+1].l<=r)
        update(index*2+1,l,r,k);
    tree[index].data=tree[index*2].data+tree[index*2+1].data;
    return ;
}
long long search(long long index, long long l, long long r) {
    if(tree[index].l >= l && tree[index].r <= r) return tree[index].data;
    push_down(index);
    long long num=0;
    if(tree[index*2].r >= l) num+=search(index*2,l,r);
    if(tree[index*2+1].l <= r) num+=search(index*2+1,l,r);
    return num;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(long long i = 1; i <= n; i++) cin >> arr[i];
    build(1, n, 1, arr);
    for(long long i = 1; i <= m; i++) {
        int op; cin >> op;
        if(op == 1) {
            long long l, r, v; cin >> l >> r >> v;
            update(1, l, r, v);
        }
        else {
            long long l, r; cin >> l >> r;
            cout << search(1, l, r) << '\n';
        }
    }
    return 0;
}

// 区间乘，区间加，区间查询（带模）
#include <bits/stdc++.h>
using namespace std;
using namespace std;

const int MAXN = 100010;
long long n, m, p;
long long input[MAXN];
struct node {
    long long l,r;
    long long sum,mlz,plz;
}tree[MAXN<<2];
inline void build(long long i, long long l, long long r) {
    tree[i].l = l;
    tree[i].r = r;
    tree[i].mlz = 1;
    if(l ==r ) {tree[i].sum = input[l]%p; return;}
    long long mid = (l+r)>>1;
    build(i<<1, l, mid);
    build(i<<1|1, mid+1, r);
    tree[i].sum = (tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return;
}
inline void pushdown(long long i) {
    long long k1 = tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum = (tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
    tree[i<<1|1].sum = (tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz = (tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz = (tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz = (tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz = (tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz = 0;
    tree[i].mlz = 1;
    return ;
}
inline void mul(long long i, long long l, long long r, long long k) {
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l >= l && tree[i].r<=r) {
        tree[i].sum = (tree[i].sum*k)%p;
        tree[i].mlz = (tree[i].mlz*k)%p;
        tree[i].plz = (tree[i].plz*k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r >= l)  mul(i<<1, l, r, k);
    if(tree[i<<1|1].l <= r)  mul(i<<1|1, l, r, k);
    tree[i].sum = (tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return;
}
inline void add(long long i, long long l, long long r, long long k) {
    if(tree[i].r<l || tree[i].l>r)  return;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum += ((tree[i].r-tree[i].l+1)*k)%p;
        tree[i].plz = (tree[i].plz+k)%p;
        return;
    }
    pushdown(i);
    if(tree[i<<1].r >= l)  add(i<<1, l, r, k);
    if(tree[i<<1|1].l <= r)  add(i<<1|1, l, r, k);
    tree[i].sum = (tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return;
}
inline long long search(long long i, long long l, long long r) {
    if(tree[i].r<l || tree[i].l>r)  return 0;
    if(tree[i].l>=l && tree[i].r<=r) return tree[i].sum;
    pushdown(i);
    long long sum = 0;
    if(tree[i<<1].r >= l)  sum+=search(i<<1, l, r)%p;
    if(tree[i<<1|1].l <= r)  sum+=search(i<<1|1, l, r)%p;
    return sum%p;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> p;
    for (long long i = 1; i <= n; ++i) cin >> input[i]; 
    build(1, 1, n); 

    for (int i = 1; i <= m; ++i) {
        long long op, l, r, v; cin >> op;
        if(op == 1) {
            cin >> l >> r >> v;
            v %= p;
            mul(1, l, r, v);
        }
        else if(op == 2) {
            cin >> l >> r >> v;
            v %= p;
            add(1, l, r, v);
        }
        else if (op == 3) {
            cin >> l >> r;
            cout << search(1, l, r) << '\n';
        }
    }
    return 0;
}

十一、可持久化数据结构

十二、单调栈

十三、差分数组

图论

一、图

1.1、图的存储结构

1.1.1、邻接矩阵

// 最大顶点数
const int V = 1000;
// 邻接矩阵的定义
// mat[i][j] 表示 顶点`i`到顶点`j`的权值
int mat[V][V];
// 邻接矩阵的初始化操作
// 假设权值为零表示没有该边
memset(mat, 0, sizeof(mat))
// 增加边
// 新增顶点`i`到顶点`j`的边，权值为`w`
mat[i][j] = w;
// 删除边
// 删除顶点`i`到顶点`j`的边
mat[i][j] = 0;
// 查询边
// 查询顶点`i`到顶点`j`的边权
mat[i][j];

1.1.2、向前星

```

#### 1.1.3、邻接表

```cpp
// 最大顶点数
const int V = 100000;
// vector实现的邻接表的定义
// 不考虑边权，存储类型为int型
vector<int> e[V];
// 邻接表的初始化操作
// 将起点为`i`的边链表全部清空
e[i].clear();
// 增加边
// 新增顶点`i`到顶点`j`的边
e[i].push_back(j);
// 查询边
e[i][0];    // 查询以`i`为起点的第一条边`i->e[i][0]`
for (int j=0; j<(int)e[i].size(); ++j) {
    if (e[i][j] == k) {     // 查询边`i->k`
        // do something.
    }
}

1.1.4、链式向前星

// 最大顶点数
const int V = 100000;
// 最大边数
const int E = 100000;
// 边结构体的定义
struct Edge {
    int to;         // 表示这条边的另外一个顶点
    int next;       // 指向下一条边的数组下标，值为-1表示没有下一条边
};
// head[i] 表示顶点`i`的第一条边的数组下标，-1表示顶点`i`没有边
int head[V];
Edge edge[E];
// 链式前向星初始化，只需要初始化顶点数组就可以了
memset(head, -1, sizeof(head));
// 增加边的方式
// 新增边 a -> b，该边的数组下标为`id`
inline void AddEdge(int a, int b, int id)
{
    edge[id].to = b;
    edge[id].next = head[a];    // 新增的边要成为顶点`a`的第一条边，而不是最后一条边
    head[a] = id;
    return;
}
// 遍历从`a`点出去的所有边
for (int i=head[a]; i!=-1; i=e[i].next) {
    // e[i] 就是你当前遍历的边 a -> e[i].to
}

1.2、图的遍历

1.2.1、深度优先遍历

//访问标志数组
int visited[MAX] = {0};

//用邻接表方式实现深度优先搜索(递归方式）
//v 传入的是第一个需要访问的顶点
void DFS(MGraph G, int v)
{
    //图的顶点的搜索指针
    ArcNode *p;
    //置已访问标记
    visited[v] = 1;
    //输出被访问顶点的编号
    printf("%d  ", v);
    //p指向顶点v的第一条弧的弧头结点
    p = G.vertices[v].firstarc;
    while (p != NULL)
    {
        //若p->adjvex顶点未访问,递归访问它
        if (visited[p->adjvex] == 0)
        {
            DFS(G, p->adjvex);
        }
        //p指向顶点v的下一条弧的弧头结点
        p = p->nextarc;
    }
}

1.2.2、广度优先遍历

#include <iostream>
#include<queue>
using namespace std;

const int MAX = 10;
//辅助队列的初始化，置空的辅助队列Q，类似二叉树的层序遍历过程
queue<int> q;
//访问标记数组
bool visited[MAX];
//图的广度优先搜索算法
void BFSTraverse(Graph G, void (*visit)(int v))
{
    int v = 0;
    //初始化访问标记的数组
    for (v = 0; v < G.vexnum; v++)
    {
        visited[v] = false;
    }
    //依次遍历整个图的结点
    for (v = 0; v < G.vexnum; v++)
    {
        //如果v尚未访问，则访问 v
        if  (!visited[v])
        {
            //把 v 顶点对应的数组下标处的元素置为真，代表已经访问了
            visited[v] = true;
            //然后v入队列，利用了队列的先进先出的性质
            q.push(v);
            //访问 v，打印处理
            cout << q.back() << " ";
            //队不为空时
            while (!q.empty())
            {
                //队头元素出队,并把这个出队的元素置为 u，类似层序遍历
                Graph *u = q.front();
                q.pop();
                //w为u的邻接顶点
                for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G,u,w))
                {
                    //w为u的尚未访问的邻接顶点
                    if (!visited[w])
                    {
                        visited[w] = true;
                        //然后 w 入队列，利用了队列的先进先出的性质
                        q.push(w);
                        //访问 w，打印处理
                        cout << q.back() << " ";
                    }//end of if
                }//end of for
            }//end of while
        }//end of if
    }// end of for
}

1.2.3、拓扑排序

```

#### 1.2.4、可行遍性

```cpp
/* 欧拉图 */

/* 哈密顿图 */

二、树

2.1、树的定义和遍历

2.1.1、相关定义

```

#### 2.1.2、树的遍历

```cpp

2.2、图的生成树

2.2.1、最小生成树

/* Prim */
using PII = std::pair<int, int>;
int prim(int x, const std::vector<std::vector<PII> > &graph) {
    // priority queue to maintain edges with respect to weights
    std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q;
    std::vector<bool> marked(graph.size(), false);
    int minimum_cost = 0;

    Q.push(std::make_pair(0, x));
    while (!Q.empty()) {
        // Select the edge with minimum weight
        PII p = Q.top();
        Q.pop();
        x = p.second;
        // Checking for cycle
        if (marked[x] == true) {
            continue;
        }
        minimum_cost += p.first;
        marked[x] = true;
        for (const PII &neighbor : graph[x]) {
            int y = neighbor.second;
            if (marked[y] == false) {
                Q.push(neighbor);
            }
        }
    }
    return minimum_cost;
}

int main(void) {
    int nodes = 0, edges = 0;
    std::cin >> nodes >> edges;  // number of nodes & edges in graph
    if (nodes == 0 || edges == 0) {
        return 0;
    }

    std::vector<std::vector<PII> > graph(nodes);

    // Edges with their nodes & weight
    for (int i = 0; i < edges; ++i) {
        int x = 0, y = 0, weight = 0;
        std::cin >> x >> y >> weight;
        graph[x].push_back(std::make_pair(weight, y));
        graph[y].push_back(std::make_pair(weight, x));
    }

    // Selecting 1 as the starting node
    int minimum_cost = prim(1, graph);
    std::cout << minimum_cost << std::endl;
    return 0;
}

/* Kruskal */

2.2.2、次小生成树

```

#### 2.2.3、最小树形图

```cpp

2.3、其它问题

2.3.1、LCA

/* 离线tarjan */

/* 在线 dfs + ST */

/* 倍增算法 */

2.3.2、最小支配集

```

#### 2.3.3、最小点覆盖

```cpp

2.3.4、最大独立集（最大完全子图）

```

## 三、最短路径问题

### 3.1、单源最短路径

#### 3.1.1、Dijkstra

```cpp

3.1.2、Bellman-Ford

```

#### 3.1.3、Spfa

```cpp

3.2、顶点间最短距离

3.2.1、Floyd

```

### 3.3、扩展问题

#### 3.3.1、k短路

```cpp

3.3.2、差分约束

```

#### 3.3.3、Floyd求最小环

```cpp

四、连通性问题

4.1、图的补图

4.2、连通度

4.2.1、点连通度

```

#### 4.2.2、割点

```cpp

4.2.3、边连通度

```

#### 4.2.4、割边

```cpp

4.3、双连通

4.3.1、双连通图

```

#### 4.3.2、双连通分支

```cpp

4.4、缩点

```

## 五、二分图

### 5.1、性质

```cpp

六、网络流

6.1、性质

```

## 七、仙人掌图

### 7.1、无向仙人掌图

#### 7.1.1、性质

```cpp

7.2、有向仙人掌图

7.2.1、定义

```

#### 7.2.2、性质

```cpp

八、2 SAT

计算几何

一、凸包

二、多边形面积&周长

三、多边形的核

四、半平面交

五、模拟退火

六、平面最近点对

七、对踵点

动态规划

一、线性DP

二、状压DP

三、区间DP

四、树形DP

五、概率DP

六、数位DP

七、背包问题

八、记忆化搜索

九、轮廓线DP

十、插头DP

组合数学

一、斐波那契数列

1.1、递推式和通项公式

```

### 1.2、性质

```cpp

1.3、数论相关

```

## 二、卢卡斯数列

### 2.1、递推式&通项公式

```cpp

三、卡特兰数

四、置换群

4.1、Burnside引理

```

### 4.2、Polya

```cpp

五、鸽巢原理

六、容斥原理

七、母函数

八、Stirling数

字符串

一、KMP

1.1、普通KMP

#include <iostream>
#include <string>

using namespace std;
const int MAXN = 1000010;
int nextarr[MAXN];
inline void getnext(string s) {
    nextarr[0] = -1;
    for (int i = 0, j = -1; i < s.length(); ) {
        while (-1!=j && s[i]!=s[j]) j = nextarr[j];
        nextarr[++i] = ++j;
    }
}

inline void kmpnext(string s) { // 优化
    nextarr[0] = -1;
    for (int i = 0, j = -1; i < s.length(); ) {
        while (-1!=j && s[i]!=s[j]) j = nextarr[j];
        if (s[++i] == s[++j]) nextarr[i] = nextarr[j];
        else nextarr[i] = j;
    }
}

int kmp(string s1, string s2) {
    int ans = 0; // 模式串在主串中出现的次数
    // getnext(s2);
    kmpnext(s2);
    for (int i = 0, j = 0; i < s1.length(); ) {
        while (-1!=j && s1[i]!=s2[j]) j = nextarr[j];
        i++, j++;
        if (j == s2.length()) {cout << i-s2.length()+1 << '\n'; ans++; j = nextarr[j];}
    }
    return ans;
}

int main(void) {
    string s1, s2; cin >> s1 >> s2;
    // cout << kmp(s1, s2) << '\n';
    kmp(s1, s2);
    for (int i = 1; i <= s2.length(); ++i) cout << nextarr[i] << ' '; cout << '\n';
    return 0;
}

1.2、扩展KMP

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 20000010;
long long nextarr[MAXN], extend[MAXN];
int s1len, s2len, slen;
inline void getnext(char* s) {
    nextarr[0] = slen;
    int j = 0, k = 1, p, len;
    while (j+1 < slen && s[j] == s[j+1]) j++;
    nextarr[1] = j;
    for (int i = 2; i < slen; ++i) {
        p = nextarr[k]+k-1;
        len = nextarr[i-k];
        if (i+len < p+1) nextarr[i] = len;
        else {
            j = max(0, p-i+1);
            while (i+j < slen && s[i+j] == s[j]) ++j;
            nextarr[i] = j;
            k = i;
        }
    }
}
inline void ekmp(char* s1, char* s2) {
    int j = 0, k = 0, p, len;
    while (j < s1len && j < s2len && s2[j] == s1[j]) ++j;
    extend[0] = j;
    for (int i = 1; i < s1len; ++i) {
        p = extend[k]+k-1;
        len = nextarr[i-k];
        if (i+len < p+1) extend[i] = len;
        else {
            j = max(0, p-i+1);
            while (i+j < s1len && j < s2len && s1[i+j] == s2[j]) j++;
            extend[i] = j;
            k = i;
        }
    }
}

char s1[MAXN], s2[MAXN]; // 字符数组比string快太多
int main(void) {
    scanf("%s", s1); scanf("%s", s2);
    s1len = strlen(s1), s2len = slen = strlen(s2);
    getnext(s2);
    ekmp(s1, s2);
    long long ans1 = 0LL, ans2 = 0LL;
    // cout << accumulate(nextarr, nextarr+s2.length(), 0) << '\n' << accumulate(extend, extend+s1.length(), 0) << '\n';
    for (int i = 0; i < s1len; ++i) ans2 ^= (i+1)*(extend[i]+1);
    for (int i = 0; i < s2len; ++i) ans1 ^= (i+1)*(nextarr[i]+1);
    cout << ans1 << '\n' << ans2 << '\n';
    return 0;
}

二、Manacher

2.1、应用

const int maxn=11000002;
char data[maxn<<1];
int p[maxn<<1],cnt,ans;
inline void qr(){
      char c=getchar();
      data[0]='~',data[cnt=1]='|';
      while(c<'a'||c>'z') c=getchar();
      while(c>='a'&&c<='z') data[++cnt]=c,data[++cnt]='|',c=getchar();
}
int main(){
      qr();
      for(int t=1,r=0,mid=0;t<=cnt;++t){
	    if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);
	    while(data[t-p[t]]==data[t+p[t]]) ++p[t];
	    //暴力拓展左右两侧,当t-p[t]==0时，由于data[0]是'~'，自动停止。故不会下标溢出。
	    //假若我这里成功暴力扩展了，就意味着到时候r会单调递增，所以manacher是线性的。
	    if(p[t]+t>r) r=p[t]+t-1,mid=t;
	    //更新mid和r,保持r是最右的才能保证我们提前确定的部分回文半径尽量多。
	    if(p[t]>ans) ans=p[t];
      }
      printf("%d\n",ans-1);
      return 0;
}

三、AC自动机

3.1、应用

```

## 四、后缀数组

### 4.1、DA后缀数组倍增算法

```cpp

4.2、DC3

```

### 4.3、应用

```cpp

五、后缀自动机

5.1、应用

```

## 六、字符串hash

### 6.1、应用

```cpp

STL

一、容器

1.1、常用容器

vector<int> v; // 向量
deque<int> d; // 双端容器
map<int, int> m; // 映射（默认有序）
multimap<int, int> mm;
unordered_map<int, int> um; // 无序
set<int, int> s; // 集合（默认有序）
multiset<int> ms;
unordered_set<int> us; // 无序
queue<int> q; // 队列
stack<int> t; // 栈
priority_queue<int> pq; // 优先队列（有序）
string s; // 字符串

1.2、操作

/* vector常用操作 */
for (auto i: vec); 
for (int i = 0; i < vec.size(); ++i); // 遍历
push_back(); insert(); // 插入
pop_back(); erase(); // 删除

/* deque常用操作 */
for (auto i: dq);
for (int i = 0; i < dq.size(); ++i); // 遍历
push_back(); push_front(); insert(); // 插入
pop_front(); pop_back(); erase(); // 删除

/* map常用操作 */
for (auto i: m) i.first, i.second;
for (auto it = m.begin(); it != m.end(); ++it) it->first, it->second; // 遍历
m[key] = val; insert(pair<int, int>); // 插入
erase(key); // 删除
find(key); // if find return iter, else return end

/* multimap常用操作 */
for (auto i: mm) i.first, i.second;
for (auto it = mm.begin(); it != mm.end()l ++it) it->first, it->second; // 遍历

lower_bound(); uppre_bound(); equal_range(); count(); find(); // 查找

multimap<keys_type, vals_type>::iterator it = mmp.find(key);
for(auto cnt = 0; cnt != mmap.count(key); cnt++, it++)
    cout << it->first << ":" << it->second << endl;

multimap<keys_type, vals_type>::iterator bg = mmp.lower_bound(key), ed = mmp.upper_bound(key);
for(auto it = bg; it != ed; it++)
    cout << it->first << ":" << it->second << endl;

multimap<keys_type, vals_type>::iterator bg = mmp.equal_range(key).first, ed = mmp.equal_range(key).second;
for(auto it = bg; it != ed; it++)
    cout << it->first << ":" << it->second << endl;

/* unordered_map常用操作 */
for (auto i: um) i.first, i.second;
for (auto it = um.begin(); it != um.end(); ++it) it->first, it->second;
um[key] = val; insert(); erase(); find(); // 插入删除

/* set常用操作 */
find(); insert(); erase(); // 插入删除
set_intersection();				//（取集合交集）
set_union();					//（取集合并集）
set_difference();				//（取集合差集）
set_symmetric_difference();		//（取集合对称差集）

/* multiset常用操作 */
find(); lower_bound(); upper_bound(); equal_range(); count(); // 查找
for (auto i: ms);
for (auto it = ms.begin(); it != ms.end(); ++it); // 遍历

/* unordered_set常用操作 */
for (auto i: us);
for (auto it = us.begin(); it != us.end(); ++it); // 遍历
insert(); find(); erase(); // 插入删除

/* queue常用操作 */
front(); back(); // 查找
push(); pop(); // 入队出队

/* priority_queue常用操作 */
push(); pop(); top(); // 优先级高的先出队（默认）

/* stack常用操作 */
push(); pop(); top(); // 压栈出栈

/* string常用操作 */
[], front(), back(); // 查找
< <= > >= == !=, compare(); // 比较
push_back(); insert(); append(); +; // 插入
tolower(), toupper(); 
transform(s.begin(), s.end(), s.begin(),[](unsigned char c) { return toupper(c); }); // 大小写

二、算法

2.1、常用算法

/* sort */
sort(begin, end, cmp);
nth_element(first, nth, last); // 将第nth位的元素放好位置
is_sorted(first, last);	// 检测是否排好序（默认升序排列）
is_sorted_until(first, last); // 比is_sorted多一个返回首个无序元素的迭代器
partial_sort(first, middle, last); // 部分排序

/* merge */
merge(first_1, last_1, first_2, last_2, res_iter); // 合并两个序列并放到容器中去
inplace_merge(first, middle, last);	// 合并两个有序部分

/* find search */
find(first, last, val);
find_if(first, last, self_rule); // 自定义查找规则
find_end(first_main, last_main, first_sub, last_sub); // 子序列最后出现的位置
search(first_main, last_main, first_sub, last_sub);	// 与find_end()相对，子序列首次出现的位置

/* partition */
partition(first, last, rule); // 按分组规则分组，返回分界线

/* bound */
upper_bound(first, last, val);		// 查找第一个大于某个元素的位置（迭代器）	
lower_bound(first, last, val);		// 查找第一个大于或等于某个元素的位置（迭代器）
equal_range(first, last, val);		// 查找某个元素所在的区间（pair<iterator, iterator>）
binary_search(first, last, val, rule);	// 返回bool值，返回是否查找到目标元素（也可自定义查找规则）

/* permutation */
next_permutation(first, last);			// 字典升序
prev_permutation(first, last);			// 字典降序
vector<int> range {1,2,3,4};	// 初始时是最小排列
do {
    for (auto i: range)    cout << i << " ";
    cout << endl;
}while(next_permutation(begin(range), end(range)));

三、操作技巧

3.1、输入输出

/* 快读快写模板 */
namespace IO    {
    template<typename T> inline T read()    {
        T x = 0, w = 1;
        char ch = getchar();
        while (!isdigit(ch))    {
            if (ch == '-')    w *= -1;
            ch = getchar();
        }
        while (isdigit(ch))    {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = getchar();
        }
        return x * w;
    }
    template<typename T> inline void write(T x, char end_ch)    {
        if (x < 0)    { 
            x = -x;
            putchar('-'); 
        }
        static int sta[101];
        int top = 0;
        do {
            sta[top++] = x % 10;
            x /= 10;
        } while (x);
        while (top)    putchar(sta[--top] + 48);
        putchar(end_ch);
    }
};

/* C-Style */
scanf("%_", &_); printf("%_", _);
%d int, %u unsigned int, %ld, long int, %lld long long int;
%c char, %s char*;
%f float, %lf double;

/* CPP-Style */
ios::sync_with_stdio(false);
cin.tie(nullptr); // 解除绑定
cin >> _; cout << _;

stringstream ss; string s;
ss << s; ss >> s

3.2、重载

/* 比较符号 */

// 自定义结构体（重载<， >类似）
bool operator<(const Node& a, const Node& b) {
    return a.x < b.x; // 结构体外重载
}
struct Node {
    int x, y;
    bool operator<(const Node& a) const {
        return this->x < a.x; // 结构体内重载
    }
}

/* << >> */
// 重载<<操作符
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p)    {
    return os << "(" << p.first << ", " << p.second << ")";
}
// 重载>>操作符
template<typename T>
istream& operator>>(istream& is, pair<T, T>& p)    {
    return is >> p.first >> p.second;
}

fetch150zy's blog

算法

算法基础

一、枚举

1.1、两数之和

二、递归分治

2.1、归并排序

三、贪心

3.1、知识点

3.2、一篇题解

四、排序

4.1、选择排序

4.2、冒泡排序

4.3、插入排序

4.4、计数排序

4.5、基数排序

4.6、快速排序

4.7、归并排序

4.8、堆排序

4.9、桶排序

4.10、希尔排序

一、二分

1.1、左闭右开

1.2、左闭右闭

二、差分&前缀和

2.1、差分数组

2.2、前缀和数组

数论

一、欧基里德及扩展

1.1、GCD

1.2、Extend_GCD

二、同余

2.1、相关概念

2.2、逆元

三、素数

3.1、素数分布

3.2、素数猜想

3.3、素数测试

3.4、算数基本定理

3.5、素数判定

3.5.1、质数筛

3.5.2、Miller素数测试

3.5.3、Meissel-Lehmer

3.6、素因子分解

四、积性函数

4.1、定义

4.2、常见类型

4.2.1、欧拉函数

4.2.2、莫比乌斯函数

五、矩阵和线性方程组

5.1、求解模线性方程组

5.2、求解线性方程组的解

六、莫比乌斯

七、阶乘

7.1、斯特林公式

八、三角形数

8.1、定义

8.2、公式

8.3、性质

九、降幂公式

十、线性基

10.1、定义

10.2、性质

10.3、构造方法

10.4、应用

十一、快速幂

11.1、快速幂

11.2、矩阵快速幂

11.3、多项式快速幂

数据结构

一、划分树

二、RMQ

三、树链剖分

四、伸展树

五、动态树

六、主席树

七、Trep

八、KD树

九、替罪羊树

十、线段树和树状数组