题解：P7164 [COCI2020-2021#1] 3D Histogram

1234567890regis · 2024-07-30 15:46:07 · 题解

本人太菜，写一个通俗易懂的非正解做法。

第一个思路是用 n^2 骗分，怎么骗分也非常简单，用 Sparse Table 即可。

于是第一部分：

void stinit()
{
    for (int i = 1; i <= n; i++) sta[i][0] = a[i], stb[i][0] = b[i];
    for (int j = 1, b = 1; j < MAXN2; j++, b <<= 1)
        for (int i = 1; i <= n - 2 * b + 1; i++)
            sta[i][j] = min(sta[i][j - 1], sta[i + b][j - 1]),
            stb[i][j] = min(stb[i][j - 1], stb[i + b][j - 1]);
}

int queryA(int l, int r)
{
    int len = log2(r - l + 1);
    return min(sta[l][len], sta[r - (1ll << len) + 1][len]);
}

int queryB(int l, int r)
{
    int len = log2(r - l + 1);
    return min(stb[l][len], stb[r - (1ll << len) + 1][len]);
}

主枚举代码：

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
        ans = max(ans, queryA(i, j) * queryB(i, j) * (j - i + 1));

做完之后，我发现一个玄学剪枝优化，具体如下：

考虑目前枚举到的最大值 ans，我发现有些枚举是不必要的。原因？因为他们再大也超过不了 ans。为什么？

以下简记 q_1 = queryA(i, j) ， q_2 = queryB(i, j) ， q = queryA(i, j) * queryB(i, j)。

现在我们枚举到 (i, j) ，希望找到下一个要枚举的 j' > j ，使得 (j' - i + 1) \times q' > ans。

而我们发现因为 query(i, j) = \min_{i \le k \le j} (a_k) \ge \min_{i \le k \le j'} (a_k) = query(i, j')

为了使他超过 ans ，必须有：

这就说明， (j, j') 这段区间是不用枚举的，因为它不可能超过 ans。

因此，程序可以优化为：

for (int i = 1; i <= n; i++)
       for (int j = i; j <= n; j++) {
           int cur = queryA(i, j) * queryB(i, j);
           ans = max(ans, cur * (j - i + 1));
           j = (ans / cur) + i - 1;
       }

玄学剪枝的复杂度能过吗？我们估算一下平均复杂度：

运算到一定程度， ans = len \times cur'

估算后发现 len \approx \in (\sqrt{n}, n)

令 t 为时间复杂度，

只要我们常数较小，是大概率能过的。

结果， TLE 了。

为什么？因为如果直接让 i 从小到大遍历 1 到 n 的话，ans 的更新速度太慢了。

为了让他更平均（这样时间复杂度更小），应该使用万能随机化函数 random_shuffle() （注：此函数在 C++17 后被弃用，改为 shuffle() ，但是作为 OIer ，管他的！）

于是让 i 遍历一个随机数组（类似于洗牌）即可！

AC 代码：

#include <iostream>
#include <vector>
#include <queue>
#include <ctime>
#include <cmath>
#include <random>
#define int long long
using namespace std;

const int MAXN = 2e5 + 7, MAXN2 = 20;
int a[MAXN], b[MAXN], sta[MAXN][MAXN2], stb[MAXN][MAXN2], n, ans;

void stinit()
{
    for (int i = 1; i <= n; i++) sta[i][0] = a[i], stb[i][0] = b[i];
    for (int j = 1, b = 1; j < MAXN2; j++, b <<= 1)
        for (int i = 1; i <= n - 2 * b + 1; i++)
            sta[i][j] = min(sta[i][j - 1], sta[i + b][j - 1]),
            stb[i][j] = min(stb[i][j - 1], stb[i + b][j - 1]);
}

int queryA(int l, int r)
{
    int len = log2(r - l + 1);
    return min(sta[l][len], sta[r - (1ll << len) + 1][len]);
}

int queryB(int l, int r)
{
    int len = log2(r - l + 1);
    return min(stb[l][len], stb[r - (1ll << len) + 1][len]);
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    vector<int> p;
    for (int i = 1; i <= n; i++) p.push_back(i);
    shuffle(p.begin(), p.end(), [](int x) { return rand() % x; });
    stinit();
    for (int i : p) 
        for (int j = i; j <= n; j++) {
            int cur = queryA(i, j) * queryB(i, j);
            ans = max(ans, cur * (j - i + 1));
            j = (ans / cur) + i - 1;
        }
    cout << ans << endl;
}