TIOJ 1965：大陸人系列1：傳說中的log

TIOJ 1965：大陸人系列1：傳說中的log

題目大意：給你 $n$ 個數字 $C_0\sim C_{n-1}$，有 $q$ 次詢問，每次問區間 $[l,r)$ 中的最大值是多少，$n\leq 10^7,q\leq 3\times 10^7$。

解法：原本要寫 $O(n)/O(1)\text{ rmq}$，但寫到一半發現太麻煩了，所以寫了一個兩層的稀疏表，每 $K$ 個數字分一塊，用一個大的稀疏表存 $\frac{n}{K}$ 塊的最大值，用 $\frac{n}{K}$ 個小稀疏表存 $K$ 個數字的最大值。$K$ 取 $256$ 在大測資時間跟空間剛好都會過，可是在小測資會被卡空間，所以小測資改用 $\text{zkw}$。$\text{AC}$ 之後我在大測資用 $\text{zkw}$ 竟然也會過?!

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include "lib1965.h"
using namespace std;

const int K = 256;

int n;
bool small;
vector<uint64_t> node;
vector<vector<uint64_t>> ST;
vector<vector<vector<uint64_t>>> st;

void init(int N, uint64_t A[]) {
    if (N <= 1e6) {
        n = N;
        small = 1;
        node.resize(n << 1);
        for (int i = 0; i < n; i++) node[n + i] = A[i];
        for (int i = n - 1; i > 0; i--) node[i] = max(node[i << 1], node[i << 1 | 1]);
        return;
    }
    n = (N + K - 1) / K * K;
    ST.emplace_back(vector<uint64_t>());
    for (int l = 0, r = K - 1; l < n; l = r + 1, r += K) {
        vector<vector<uint64_t>> cur;
        cur.emplace_back(vector<uint64_t>());
        for (int i = l; i <= r; i++) cur.back().emplace_back(i < N ? A[i] : 0);
        for (int len = 2; len <= K; len <<= 1) {
            cur.emplace_back(vector<uint64_t>());
            for (int i = l; i + len - 1 <= r; i++) cur.back().emplace_back(max(cur.end()[-2][i - l], cur.end()[-2][i + (len >> 1) - l]));
        }
        st.emplace_back(vector<vector<uint64_t>>());
        swap(cur, st.back());
        ST.back().emplace_back(*max_element(A + l, A + min(N - 1, r) + 1));
    }
    int sz = ST[0].size();
    for (int len = 2; len <= sz; len <<= 1) {
        ST.emplace_back(vector<uint64_t>());
        for (int i = 0; i + len < sz; i++) ST.back().emplace_back(max(ST.end()[-2][i], ST.end()[-2][i + (len >> 1)]));
    }
}

uint64_t RMQ(int l, int r) {
    if (small) {
        uint64_t val = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) val = max(val, node[l++]);
            if (r & 1) val = max(val, node[--r]);
        }
        return val;
    }
    r--;
    int L = l / K, R = r / K;
    if (L == R) {
        int h = __lg(r - l + 1);
        return max(st[L][h][l - K * L], st[R][h][r - (1 << h) + 1 - K * R]);
    }
    uint64_t val = 0;
    int h;
    h = __lg(K * (L + 1) - l);
    val = max(val, max(st[L][h][l - K * L], st[L][h][K - (1 << h)]));
    h = __lg(r - K * R + 1);
    val = max(val, max(st[R][h][0], st[R][h][r - (1 << h) + 1 - K * R]));
    L++, R--;
    if (L <= R) {
        h = __lg(R - L + 1);
        val = max(val, max(ST[h][L], ST[h][R - (1 << h) + 1]));
    }
    return val;
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！