P3793 题解

· · 题解

科技选手用阉割版四毛子过了这题。目前这玩意好像还没有名字，姑且叫他二毛子。

首先还是分块，块长为 B=\log n。块间建 st 表，时空复杂度为 O(\frac nB\log\frac nB)=O(n)。如果一个询问的左右端点在不同块，必然可以将其拆成 块后缀+整块+前缀 的形式。预处理出每个块的前后缀最大值即可 O(1) 查询。那如果两个端点在同一块块内呢？

考虑原版四毛子是怎么处理的。得益于 +1-1 RMQ 优美的性质，我们可以预处理出所有本质不同的序列的最大值 位置。而对于一般的序列，我们也可以找到类似的指标。

不妨来考虑所有可能成为最大值的位置。为了方便预处理，我们考虑块内一个 [1,r] 的前缀。对于它的任意后缀，可能成为最大值的位置只有可能是 后缀最大值 出现的位置。这里后缀最大值位置定义为所有满足 a_l>\max_{l<i\le r}a_i 的 l。

然后我们把每个后缀最大值的位置 b_1,b_2,\cdots,b_k 拉下来，可以得到两个性质：

可能成为最大值的位置构成了一个单调递减的子序列，所以当前后缀的最大值，就是该子序列在后缀里的第一个数，也就是：

可以发现，最大值的位置正好是前缀单调栈。我们可以使用单调递减的单调栈扫一遍进行预处理。由于块长 \log n，完全可以将单调栈位置进行二进制压位。查询时可以通过位运算删掉 <l 的位置，再计算 lowbit 得到答案位置。这部分的时间复杂度也是 O(n)-O(1) 的，可以通过。

值得注意的是这算法偏序了一般的四毛子算法，在常数和码量上都更胜一筹，实用性也没的说。另外，由于块长 \log n 的特性，完全可以将块长设为 64 之类的整数，这样求块的编号等都可以用位移完成。实测跑的非常快。

最后来说下这个名字的含义。四毛子由建笛卡尔树、拍欧拉序、分块建 st 表，压位预处理组成。本算法知保留了最后两个部分，因此叫二毛子算法。很厉害吧！

啊啊啊这好像是唯一一篇确定性算法啊你们这些随机化批！！！

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;

const int MAXN = 2e7 + 10;
const int MAXM = 3.2e5 + 10;

uint _z1, _z2, _z3, _z4, _b;

inline 
void srand(uint x) {
    _z1 = x, _z2 = ~x ^ 0x233333333u;
    _z3 = x ^ 0x1234598766U, _z4 = ~x + 51;
}

inline 
uint _rand() {
    _b = (_z1 ^ _z1 << 6) >> 13, _z1 = _b ^ (_z1 & 4294967294u) << 18;
    _b = (_z2 ^ _z2 << 2) >> 27, _z2 = _b ^ (_z2 & 4294967288u) << 2;
    _b = (_z3 ^ _z3 << 13) >> 21, _z3 = _b ^ (_z3 & 4294967280u) << 7;
    _b = (_z4 ^ _z4 << 3) >> 12, _z4 = _b ^ (_z4 & 4294967168u) << 13;
    return _z1 ^ _z2 ^ _z3 ^ _z4;
}

inline 
int get() {
    int a = _rand() & 32767, b = _rand() & 32767;
    return a << 15 | b;
}

#define l(i) ((i - 1) << 6 | 1)
#define r(i) (i << 6)
#define bel(i) (i + 63 >> 6)

int n, m, a[MAXN], len, tot, lgn;

int f[19][MAXM], pre[MAXN], suf[MAXN];

ull val[MAXN]; int s[30], top;

inline 
void build() {
    len = 64, tot = bel(n), lgn = __lg(tot);
    for (int i = 1; i <= tot; i++) {
        pre[l(i)] = a[l(i)], suf[r(i)] = a[r(i)];
        for (int j = l(i) + 1; j <= r(i); j++) pre[j] = max(pre[j - 1], a[j]);
        for (int j = r(i) - 1; j >= l(i); j--) suf[j] = max(suf[j + 1], a[j]);
        for (int j = l(i); j <= r(i); j++) f[0][i] = max(f[0][i], a[j]);
    }
    for (int j = 0; j < lgn; j++) {
        for (int i = 2 << j; i <= tot; i++) {
            f[j + 1][i] = max(f[j][i - (1 << j)], f[j][i]);
        }
    }
    for (int i = 1; i <= tot; i++) {
        top = 0;
        for (int j = l(i); j <= r(i); j++) {
            if (j > l(i)) val[j] = val[j - 1];
            for (; top && a[j] >= a[s[top]]; val[j] ^= 1ull << s[top--] - l(i));
            s[++top] = j, val[j] |= 1ull << j - l(i);
        }
    }
}

inline 
int query(int ql, int qr) {
    int p = bel(ql), q = bel(qr);
    if (p == q) return a[ql + __builtin_ctzll(val[qr] >> ql - l(p))];
    int ans = max(suf[ql], pre[qr]);
    if (p + 1 < q) {
        int k = __lg(q - p - 1);
        ans = max(ans, f[k][p + (1 << k)]);
        ans = max(ans, f[k][q - 1]);
    }
    return ans;
}

uint seed; ull ans;

int main() {
    scanf("%d%d%u", &n, &m, &seed), srand(seed);
    for (int i = 1; i <= n; i++) a[i] = get(); build();
    for (int ql, qr, i = 0; i < m; i++) {
        ql = get() % n + 1, qr = get() % n + 1;
        if (ql > qr) swap(ql, qr);
        ans += query(ql, qr); 
    }
    printf("%llu", ans);
}