[COCI 2023/2024 #2] Zatopljenje 题解

ToBeDetermined · 2024-10-19 15:13:03 · 题解

闲话

考前集训，每日一练做到的题，~我写挂了五次~。自己想到分块的做法，看题解区没有，于是来发一篇。

思路

我们注意到，当海水高度为 x 时，区间 [l, r] 的小岛的个数可以这么计算：

所以第 i 个位置产生贡献当且仅当 h_i \le x \lt h_{i + 1} ，考虑分块并预处理出每个块的答案。由于 0 \le h_i, x_i \le 10^9 ，所以要离散化。时间复杂度 O((n + q)(\sqrt{n} + \log{n})) ，虽然比不上线段树或树状数组，但是思路还是比较好想的。

具体细节见代码实现。

Tip : 不要开long long，不然会MLE。

Code

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x) {
    int neg = 1;
    char ch;
    while(ch = getchar(), !isdigit(ch)) if(ch == '-') neg = -1;
    x = ch - '0';
    while(ch = getchar(), isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ '0');
    x *= neg;
    return;
}
// bans[i][j] : 第 i 个块当 x = j 时的答案
int n, q, a[200005], blk, cnt, bans[505][200005], x, l, r;
PII p[200005];
signed main() {
    read(n), read(q);
    for(int i = 1; i <= n; ++i) read(a[i]);
    // 加一个 0 ，方便离散化
    a[0] = 0, ++n;
    // 离散化
    for(int i = 0; i < n; ++i) p[i] = {a[i], i};
    sort(p, p + n);
    for(int i = 0; i < n; ++i) {
        if(i == 0) a[p[i].second] = 1;
        else {
            if(p[i].first == p[i - 1].first) a[p[i].second] = a[p[i - 1].second];
            else a[p[i].second] = a[p[i - 1].second] + 1;
        }
    }
    // 分块
    blk = sqrt(n);
    cnt = (n - 1) / blk + 1;
    for(int i = 0; i < n - 1; ++i) if(a[i] < a[i + 1]) {
            // 差分计算答案
            ++bans[i / blk][a[i]];
            --bans[i / blk][a[i + 1]];
        }
    // 前缀和
    for(int i = 0; i < cnt; ++i) for(int j = 1; j <= n; ++j) bans[i][j] += bans[i][j - 1];
    while(q--) {
        read(l), read(r), read(x);
        // 对 x 离散化，找到最后一个小于等于 x 的值
        int ind = lower_bound(p, p + n, (PII){x + 1, 0}) - p, ans;
        x = a[p[ind - 1].second];
        // l 点的答案
        ans = a[l] > x;
        if(l / blk == r / blk) {
            // 在同一个块中
            for(int i = l; i < r; ++i) ans += (a[i] <= x && a[i + 1] > x);
        }
        else {
            // 计算 l 所在块的答案
            for(int i = l; i < (l / blk + 1) * blk; ++i) ans += (a[i] <= x && a[i + 1] > x);
            // 计算 r 所在块的答案
            for(int i = r / blk * blk; i < r; ++i) ans += (a[i] <= x && a[i + 1] > x);
            // 计算中间块的答案
            for(int i = l / blk + 1; i < r / blk; ++i)ans += bans[i][x];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Submisson

完结撒花！！！✿✿ヽ(°▽°)ノ✿