U267084 测试ST表的速度

出一点简单的题目吧，前面出的题目都太难了。 对 ST 表的测试，同时是对评测机的测试。

给定一个序列，求区间最小值、最大值。

无

无

对于 $30\%$ 的数据，$1\leq n,m\leq10^4$； 对于 $60\%$ 的数据，$1\leq n,m\leq5\times 10^6$； 对于 $100\%$ 的数据，$1\leq n,m\leq10^7$。 ### 本题的模板程序 #### C++ ```cpp // clang-format on #include #include unsigned int u32_hasher(unsigned int x) { return x *= 0xeb382d69u, x ^= x >> 23, x *= 0xeb382d69u, x ^= x >> 23, x *= 0xeb382d69u, x ^= x >> 23, x * 0xeb382d69u; } static unsigned int seed; unsigned int next_integer() { return seed += u32_hasher(seed); } unsigned long long u64_hasher(unsigned long long x) { return x *= 0x1952BB648B74B19Eull, x ^= x >> 47, x *= 0x1952BB648B74B19Eull, x ^= x >> 47, x *= 0x1952BB648B74B19Eull, x ^= x >> 47, x * 0x1952BB648B74B19Eull; } void output_arr(unsigned long long* first, unsigned long long* last) { int siz = last - first; int blk = siz / 4; unsigned long long ret = siz; unsigned long long x = 1871030361u; for (int i = 0; i < blk; i++) { ret ^= (first[i] + x); x = u64_hasher(x); } printf("%llu\n", ret); } struct question { int op, l, r; }; int main() { unsigned int n, m; scanf("%u%u%u", &n, &m, &seed); unsigned int* arr = new unsigned int[n]; for (unsigned int i = 0; i < n; i++) arr[i] = next_integer(); question* q = new question[m]; for (unsigned int i = 0; i < m; i++) { q[i].op = next_integer() & 1; q[i].l = next_integer() % n; q[i].r = next_integer() % n; if (q[i].l > q[i].r) { unsigned int t = q[i].l; q[i].l = q[i].r; q[i].r = t; } } unsigned int* ret = new unsigned int[m]; // solve(n, m, arr, q, ret); output_arr((unsigned long long*)ret, (unsigned long long*)(ret + m)); delete[] arr; delete[] q; delete[] ret; return 0; } ``` #### C ```c #include #include unsigned int u32_hasher(unsigned int x) { return x *= 0xeb382d69u, x ^= x >> 23, x *= 0xeb382d69u, x ^= x >> 23, x *= 0xeb382d69u, x ^= x >> 23, x * 0xeb382d69u; } static unsigned int seed; unsigned int next_integer() { return seed += u32_hasher(seed); } unsigned long long u64_hasher(unsigned long long x) { return x *= 0x1952BB648B74B19Eull, x ^= x >> 47, x *= 0x1952BB648B74B19Eull, x ^= x >> 47, x *= 0x1952BB648B74B19Eull, x ^= x >> 47, x * 0x1952BB648B74B19Eull; } void output_arr(unsigned long long* first, unsigned long long* last) { int siz = last - first; int blk = siz / 4; unsigned long long ret = siz; unsigned long long x = 1871030361u; for (int i = 0; i < blk; i++) { ret ^= (first[i] + x); x = u64_hasher(x); } printf("%llu\n", ret); } typedef struct question { int op, l, r; } question; int main() { unsigned int n, m; scanf("%u%u%u", &n, &m, &seed); unsigned int* arr = (unsigned int*)malloc(n * sizeof(unsigned int)); for (unsigned int i = 0; i < n; i++) arr[i] = next_integer(); struct question* q = (struct question*)malloc(m * sizeof(struct question)); for (unsigned int i = 0; i < m; i++) { q[i].op = next_integer() & 1; q[i].l = next_integer() % n; q[i].r = next_integer() % n; if (q[i].l > q[i].r) { unsigned int t = q[i].l; q[i].l = q[i].r; q[i].r = t; } } unsigned int* ret = (unsigned int*)malloc(m * sizeof(unsigned int)); // solve(n, m, arr, q, ret); output_arr((unsigned long long*)ret, (unsigned long long*)(ret + m)); free(arr); free(q); free(ret); return 0; } ``` 说明：当 `q[i].op = 1` 时为查询区间最大值，反之亦然。