题解：P9461 「EZEC-14」众数 II

· · 题解

很有趣的一个题，下面说一下我做题的流程和思路来源。与大部分题解不同，本题解复杂度与值域无关，固定 O(n) 且常数较小，一发就是当时的次优解。

定义 f(i,j) 为 [b_{i\dots j}] 的最小众数，先打个四次方暴力打表。

for (int i = 0; i < b.size(); i++) {
    for (int j = 0; j < i; j++) {
        cout << "0\t";
    }
    memset(buc, 0, sizeof(buc));
    int ans = 0;
    for (int j = i; j < b.size(); j++) {
        if (++buc[b[j]] > buc[ans] || (buc[b[j]] == buc[ans] && b[j] < ans)) {
            ans = b[j];
        }
        ansans += ans;
        cout << ans << '\t';
    }
    ans %= mod;
    cout << endl;
}

观察发现 f(i,j)\in\{1,b_i\}，当且仅当 b_j\ge b_i 且 [b_i,b_j] 中间夹着的一些的 a 没有比 b_i 小的。这个结论可以证明，分讨即可，不证了。于是我们打出来还是四次方的暴力验证上面结论的正确性。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= a[i]; j++) {
        ansans += j * (a[i] - j + 1);
    }
    int minn = INF;
    for (int j = i + 1; j <= n; j++) {
        minn = min(minn, a[j]);
        for (int k = 1; k <= a[i]; k++) {
            for (int l = 1; l <= a[j]; l++) {
                if (minn < k || l < k) {
                    ansans++;
                } else {
                    ansans += k;
                }
            }
        }
    }
}

我们一步步对着新的看起来更有前途的四次方代码优化，发现最终的答案可以如下计算得到：

for (int i = 1; i <= n; i++) {
    ansans += inv2 * a[i] * (a[i] + 1) * (a[i] + 1);
    ansans -= inv6 * a[i] * (a[i] + 1) * (a[i] * 2 + 1);
    int minn = a[i];
    for (int j = i + 1; j <= n; j++) {
        minn = min(minn, a[j]);
        ansans += -inv3 * minn * minn * minn;
        ansans += inv2 * minn * minn;
        ansans += -inv6 * minn;
        ansans += inv2 * minn * minn * a[j];
        ansans += -inv2 * minn * a[j];
    }
    ansans += a[i] * (suma - s[i]);
}

单层循环内计算的东西并不占用太多时间，双层循环中计算的那些东西只有可以建立小根笛卡尔树解决。

为了统计双层循环中计算的所有东西，我们需要知道：

\sum_{i=1}^{n-1}\sum_{j=i+1}^n\min_{k=i}^ja_k \sum_{i=1}^{n-1}\sum_{j=i+1}^n(\min_{k=i}^ja_k)^2 \sum_{i=1}^{n-1}\sum_{j=i+1}^n(\min_{k=i}^ja_k)^3 \sum_{i=1}^{n-1}\sum_{j=i+1}^na_j\times\min_{k=i}^ja_k \sum_{i=1}^{n-1}\sum_{j=i+1}^na_j\times(\min_{k=i}^ja_k)^2

我们建立出小根笛卡尔树之后，就可以知道每一个元素作为最小值时的 i 的范围和 j 的范围，于是就知道元素作为最小值时的区间数量，同时使用前缀和也可以快速计算后两个东西。

#define MAXN 1000005
int n, ls[MAXN], rs[MAXN], sta[MAXN], statop;
long long a[MAXN];
mint suma, ansans, s[MAXN];
mint ans1, ans2, ans3, ans4, ans5;
void solve(long long id, long long l, long long r) {
    ans1 += mint(a[id]) * ((id - l + 1) * (r - id + 1) - 1);
    ans2 += mint(a[id]) * a[id] * ((id - l + 1) * (r - id + 1) - 1);
    ans3 += mint(a[id]) * a[id] * a[id] * ((id - l + 1) * (r - id + 1) - 1);
    ans4 += mint(a[id]) * (s[r] - s[id - 1]) * (id - l + 1) - mint(a[id]) * a[id];
    ans5 += mint(a[id]) * a[id] * (s[r] - s[id - 1]) * (id - l + 1) - mint(a[id]) * a[id] * a[id];
    if (ls[id]) {
        solve(ls[id], l, id - 1);
    }
    if (rs[id]) {
        solve(rs[id], id + 1, r);
    }
}
signed main() {
    ewin >> n;
    for (int i = 1; i <= n; i++) {
        ewin >> a[i];
        suma += a[i];
        s[i] = s[i - 1] + a[i];
    }
    sta[0] = statop = 1;
    for (int i = 1; i <= n; i++) {
        ansans += mint(a[i]) * (a[i] + 1) * (a[i] + 1) * 499122177;
        ansans -= mint(a[i]) * (a[i] + 1) * (a[i] * 2 + 1) * 166374059;
        ansans += mint(a[i]) * (suma - s[i]);
        if (i > 1) {
            while (statop && a[sta[statop - 1]] > a[i]) {
                rs[sta[statop - 1]] = ls[i];
                ls[i] = sta[--statop];
            }
            if (statop) rs[sta[statop - 1]] = i;
            sta[statop++] = i;
        }
    }
    solve(sta[0], 1, n);
    ansans -= ans1 * 166374059;
    ansans += ans2 * 499122177;
    ansans -= ans3 * 332748118;
    ansans -= ans4 * 499122177;
    ansans += ans5 * 499122177;
    cout << ansans << endl;
    return 0;
}