Theme NexT works best with JavaScript enabled

算法竞赛相关模板

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

快速读入

1
2
3
4
5
6
7
8
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)。

快速输出

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

使用了template,这样即可输出任意的整数类型(包括__int128)。

离散化

1
2
3
4
5
6
7
8
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表

1
2
3
4
5
6
7
8
9
10
11
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]);
}