算法竞赛相关模板

本文包括算法竞赛中常用的一些算法模板

快速读入

template <typename _tp>
inline void read(_tp& x) {
    char ch = getchar(), sgn = 0;
    while (ch ^ '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') ch = getchar(), sgn = 1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if (sgn) x = -x;
}

使用了template，这样即可读入任意的整数类型（包括__int128）。

快速输出

template <typename _tp>
inline void print(_tp x) {
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

使用了template，这样即可输出任意的整数类型（包括__int128）。

离散化

int disperse(int a[], int n) {
    int b[n + 1];
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    return m;
}

离散化后 $a$ 数组即变为离散化后的数组，该函数的返回值即为离散化后数组元素的种类。

ST表

int a[N], st[N][M];
void init(int n) {
    for (int i = 0; i < n; i++) st[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
    int k = (int)(log((double)(r - l + 1)) / log(2.0));
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}