（而且空间上可能有点过不去？）

lxl 提供了一种分块思想的 rmq，可以让预处理复杂度做到 $O(n)$，单次询问复杂度一般为 $O(1)$，最坏为 $O(\log _ 2 n)$

#include <bits/stdc++.h>

#define NS (20000005)
#define LGS (20)
#define BS (64)

using namespace std;

namespace GenHelper
{
unsigned z1, z2, z3, z4, b;
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);
}
}

void srand(unsigned x)
{
using namespace GenHelper;
z1 = x;
z2 = (~x) ^ 0x233333333U;
z3 = x ^ 0x1234598766U;
z4 = (~x) + 51;
}

{
using namespace GenHelper;
unsigned a = rand_() & 32767;
unsigned b = rand_() & 32767;
return a * 32768 + b;
}

inline int Max(const int a, const int b) { return a > b ? a : b; }

int n, m, k;

unsigned A[NS], pre[NS], suf[NS], lg[NS / BS + 5], st[LGS][NS / BS + 5];

unsigned long long ans;

void build()
{
for (int i = 0; i < n; i += 1)
if (!(i % BS)) pre[i] = A[i];
else pre[i] = Max(pre[i - 1], A[i]);
for (int i = n - 1; i >= 0; i -= 1)
if (!((i + 1) % BS)) suf[i] = A[i];
else suf[i] = Max(suf[i + 1], A[i]);
for (int i = 0; i < k; i += 1) st[0][i] = suf[i * BS];
for (int i = 2; i <= k; i += 1)
if (i == (1 << (lg[i - 1] + 1))) lg[i] = lg[i - 1] + 1;
else lg[i] = lg[i - 1];
for (int l = 1; (1 << l) <= k; l += 1)
for (int i = 0; i + (1 << l) <= k; i += 1)
st[l][i] = Max(st[l - 1][i], st[l - 1][i + (1 << (l - 1))]);
}

void rmq(int l, int r)
{
if (l > r) swap(l, r);
static unsigned res;
res = 0;
if (l / BS == r / BS)
for (int i = l; i <= r; i += 1) res = Max(res, A[i]);
else
{
res = Max(suf[l], pre[r]), l = l / BS + 1, r = r / BS - 1;
if (l <= r)
{
static unsigned k;
k = lg[r - l + 1];
res = Max(res, Max(st[k][l], st[k][r - (1 << k) + 1]));
}
}
ans += res;
}

int main(int argc, char const* argv[])
{
unsigned s;
scanf("%d%d%u", &n, &m, &s), k = n / BS + 1, srand(s);
for (int i = 0; i < n; i += 1) A[i] = read();
build();
unsigned l, r;
while (m--) l = read() % n, r = read() % n, rmq(l, r);
printf("%llu\n", ans);
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 2 条评论

lxl?

#### Remmina · 2019年3月29日 9:22 下午

已修正，很抱歉 QAQ
（主要是 Code+群里天天刷 llx 就口误写错了）