Submission #58910736

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using u128 = __uint128_t;
int lg(int x) { return bit_width<unsigned>(x) - 1; }

const u64 MOD = LLONG_MAX / 4;
u64 add(u64 a, u64 b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
u64 mul(u64 a, u64 b) {
    u128 x = (u128)a * (b << 3);
    return add(u64(x >> 64), u64(x) >> 3);
}
struct Affine {
    u64 a, b; // ax + b
    friend Affine operator*(const Affine& L, Affine R) {
        R.b = add(R.b, mul(L.b, R.a));
        R.a = mul(R.a, L.a);
        return R;
    }
    friend auto operator<=>(const Affine&, const Affine&) = default;
};

u64 rnd() {
    static random_device r;
    return (u64(r()) << 32 | r()) % MOD;
}
const u64 base = rnd();
const Affine LEFT = {base, rnd()}, CENTER = {base, rnd()}, RIGHT = {base, rnd()};
const Affine E = {1, 0};

struct SegTree {
    int N;
    vector<Affine> seg;
    SegTree(int N_) : N(N_), seg(2 * N, E) {}
    void set(int i, Affine x) {
        i += N;
        seg[i] = x;
        while (i >>= 1) seg[i] = seg[i << 1] * seg[i << 1 | 1];
    }
    Affine get(int L, int R) {
        Affine resL = E, resR = E;
        for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
            if (L & 1) resL = resL * seg[L++];
            if (R & 1) resR = seg[--R] * resR;
        }
        return resL * resR;
    }
};
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int& a : A) cin >> a;

    // Sparse Table (min)
    vector ST(lg(N) + 1, vector<u64>(N));
    for (int i = 0; i < N; i++) ST[0][i] = u64(A[i]) << 32 | i;
    for (int w = 0; w + 1 < size(ST); w++) {
        for (int i = 0; i + (2 << w) <= N; i++) ST[w + 1][i] = min(ST[w][i], ST[w][i + (1 << w)]);
    }
    auto get = [&](int L, int R) {
        assert(0 <= L && L < R && R <= N);
        const int w = lg(R - L);
        const u64 mn = min(ST[w][L], ST[w][R - (1 << w)]);
        return (int)mn;
    };

    // construct Cartesian Tree
    vector<array<int, 3>> tree(N);
    {
        auto dfs = [&](auto dfs, int L, int R) -> void {
            assert(0 <= L && L < R && R <= N);
            static int id = 0;
            const int mid = get(L, R);
            tree[mid][0] = id++;
            if (L < mid) dfs(dfs, L, mid);
            tree[mid][1] = id++;
            if (mid + 1 < R) dfs(dfs, mid + 1, R);
            tree[mid][2] = id;
        };
        dfs(dfs, 0, N);
    }

    // query
    int Q;
    cin >> Q;
    vector queries(Q, pair{0, 0});
    vector hash(Q, array{E, E});
    for (auto& [L, R] : queries) {
        cin >> L >> R;
        L--;
    }

    {
        vector<int> idx(Q);
        iota(begin(idx), end(idx), 0);
        ranges::sort(idx, greater<>{}, [&](int i) { return queries[i].second; });
        SegTree seg(N * 2);
        for (int R = 0; R < N; R++) {
            seg.set(tree[R][0], LEFT);
            seg.set(tree[R][1], CENTER);
            // seg.set(tree[R][2], RIGHT);
            while(size(idx) && queries[idx.back()].second == R + 1) {
                const int i = idx.back();
                idx.pop_back();
                const auto [L, R] = queries[i];
                const int mid = get(L, R);
                auto [l, m, r] = tree[mid];
                hash[i][1] = seg.get(m + 1, r);
            }
        }
    }

    {
        vector<int> idx(Q);
        iota(begin(idx), end(idx), 0);
        ranges::sort(idx, {}, [&](int i) { return queries[i].first; });
        SegTree seg(N * 2);
        for (int L = N; L--; ) {
            seg.set(tree[L][0], LEFT);
            seg.set(tree[L][1], CENTER);
            // seg.set(tree[L][2], RIGHT);
            while(size(idx) && queries[idx.back()].first == L) {
                const int i = idx.back();
                idx.pop_back();
                const auto [L, R] = queries[i];
                const int mid = get(L, R);
                auto [l, m, r] = tree[mid];
                hash[i][0] = seg.get(l + 1, m);
            }
        }
    }
    
    ranges::sort(hash);
    auto [l, r] = ranges::unique(hash);

    cout << (l - begin(hash)) << endl;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:63:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<long unsigned int>, std::allocator<std::vector<long unsigned int> > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   63 |     for (int w = 0; w + 1 < size(ST); w++) {
      |                     ~~~~~~^~~~~~~~~~

Judge Result