【算法】分块 rmq

今天无意中碰到这么一道题：

由乃救爷爷

~~作为一个 WOT 玩家感觉题面十分亲切~~

~~值得一提的是我还真和 lxl 语音联机打过 WOT~~

题目就是裸的 RMQ 问题

然而数据非常大，普通的 $O(n \log _ 2 n)-O(1)$ rmq 肯定是无法通过得了的

笛卡尔树欧拉序 $\pm$ rmq 的 $O(n)-O(1)$ 太复杂了

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

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

做法就是把序列分块，块大小为 $\log _ 2 n$ ，在块与块之间用普通 rmq 维护块间最大值，块间 rmq 预处理复杂度为 $O(\frac {n \log _ 2 \frac n {\log _ 2 n}} {\log _ 2 n}) < O(n)$

然后每个块再维护一下块内前缀最大和后缀最大

询问的时候对于询问区间中间的整块用块间 rmq 询问最大值，边上的不足一整块的用前缀/后缀最大询问一下，询问一次是 $O(1)$ 的

这样看起来很棒棒，然而有个非常奇妙的问题——如果询问的两端点在同一个块内就 GG 了

如果在同一个块内就只好暴力算答案，由于块大小为 $\log _ 2 n$ ，所以这样询问复杂度最坏是 $O(\log _ 2 n)$ 的

但是一般出题人不会卡这个算法，卡也不太好卡，你可以微调分块大小让出题人无从下手

而且这题数据又是随机的，因此可以随便做啦！

我分块习惯分成 $2 ^ k$ 这样的大小，因为编译器会对 $2 ^ k$ 这样的数字的取模和除法做优化，会快一些

但这题还是有点卡常，我把块大小开到 $64$ 才过

代码：

#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;
}

unsigned read()
{
    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;
}