此题也可以在 U267084 提交。

题目背景

出一点简单的题目吧，前面出的题目都太难了。

对 ST 表的测试，同时是对评测机的测试。

题目描述

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

输入格式

第一行有 $3$ 个数 $n,m,seed$，分别为序列长度、操作次数、随机数生成器种子。

下方提供了模板程序，供使用。

输出格式

输出 $m$ 行，为查询结果。

样例 #1

样例输入 #1

1000 1000 23742

样例输出 #1

13566418324976644511

样例 #2

样例输入 #2

1000000 1000000 3456483728

样例输出 #2

17810025793393830359

样例 #3

样例输入 #3

10000000 10000000 3456483728

样例输出 #3

13622093020693861709

提示

对于 $30\%$ 的数据，$1\leq n,m\leq10^4$；
对于 $60\%$ 的数据，$1\leq n,m\leq5\times 10^6$；
对于 $100\%$ 的数据，$1\leq n,m\leq10^7$。

本题的模板程序

C++

// clang-format on
#include <cstdio>
#include <algorithm>
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

#include <stdio.h>
#include <stdlib.h>
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 时为查询区间最大值，反之亦然。