intdisperse(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]; voidinit(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]); } intquery(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]); }