代码

#include <bits/stdc++.h>

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    inline unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
inline void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
inline int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

const int N = 2e7 + 233;
int A[N], ls[N], rs[N], stk[N], top, root;
unsigned long long ans[N];

inline void prework(unsigned n) {
  for (unsigned i = 1; i <= n; ++i) {
    while (top && A[stk[top]] <= A[i])
      ls[i] = stk[top--];
    rs[stk[top]] = i;
    stk[++top] = i;
  }
  root = stk[1];
}

inline unsigned query(int l, int r) {
  for (int x = root; ; x = r < x ? ls[x] : rs[x])
    if (l <= x && r >= x)
      return A[x];
}


int main() {
  unsigned n, m; unsigned s;
  // std::cin >> n >> m >> s;
  n = 20000000;
  m = 20000000;
  s = 233;
  srand(s);
  for (unsigned i = 1; i <= n; ++i)
    A[i] = read();
  prework(n);
  for (unsigned i = 1; i <= m; ++i) {
    int l = read() % n + 1, r = read() % n + 1;
    unsigned long long tmp = query(l <= r ? l : r, l <= r ? r : l);
    ans[i] = tmp;
    // printf("%lld\n", ans[i]);
  }
  for (int i = 1; i <= m; ++i)
      printf("%lld\n", ans[i]);
  return 0;
}

评测结果