Language: C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <climits>
#include <cassert>
#include <random>

using namespace std;

struct bit_vector {
    using u64 = uint64_t;

    int length, block_num;
    int block_width = 64;
    vector<u64> bit;
    vector<int> block;

    bit_vector(int length) : length(length) {
        block_num = (length + 63) >> 6;
        bit.resize(block_num + 1);
        block.resize(block_num + 1);
    }

    void set(int pos) { bit[pos >> 6] |= 1ULL << (pos & 63); }

    void build() {
        for (int i = 0; i < block_num; ++i)
            block[i+1] = block[i] + __builtin_popcountll(bit[i]);
    }

    bool operator[](int pos) const { return (bit[pos >> 6] >> (pos & 63)) & 1; }

    // [0, r)
    int rank(bool x, int r) const {
        int one = block[r >> 6] + __builtin_popcountll(bit[r >> 6] & ((1ULL << (r & 63)) - 1));
        return x ? one : r - one;
    }

    // [l, r)
    int rank(bool x, int l, int r) const { return rank(x, r) - rank(x, l); }

    // min r s.t. l <= r && rank(x, l, r) == k;
    int select(bool x, int l, int k) const {
        if (k == 0) return l;
        if (rank(x, l, length) < k) return length + 1;
        int ng = l, ok = length;
        while (ok - ng > 1) {
            int mid = (ok + ng) >> 1;
            if (rank(x, l, mid) >= k) ok = mid;
            else ng = mid;
        }
        return ok;
    }
};

template<typename T>
struct wavelet_matrix {
    int maxlog, length;
    vector<bit_vector> matrix;
    vector<int> zero_num;
    vector<int> l_pos;

    wavelet_matrix(vector<T> data) : length(data.size()) {
        assert(!data.empty());
        T min_value = *min_element(data.begin(), data.end());
        T max_value = *max_element(data.begin(), data.end());
        assert(0 <= min_value);
        maxlog = (max_value == 0 ? 1 : sizeof(long long int) * CHAR_BIT - __builtin_clzll(max_value));
        matrix.resize(maxlog, bit_vector(length));
        zero_num.resize(maxlog);
        l_pos.resize(maxlog);

        for (int depth = 0; depth < maxlog; ++depth) {
            vector<T> zero, one;
            for (int i = 0; i < length; ++i) {
                if ((data[i] >> (maxlog - 1 - depth)) & 1) {
                    one.push_back(data[i]);
                    matrix[depth].set(i);
                } else zero.push_back(data[i]);
            }
            matrix[depth].build();
            zero_num[depth] = zero.size();
            if (depth == maxlog - 1) break;
            data = move(zero);
            data.insert(data.end(), one.begin(), one.end());
        }
    }

    T access(int i) const {
        T res = 0;
        for (int depth = 0; depth < maxlog; ++depth) {
            bool bit = matrix[depth][i];
            res = (res << 1) | bit;
            i = matrix[depth].rank(bit, i) + zero_num[depth] * bit;
        }
        return res;
    }

    int rank(T x, int l, int r) {
        for (int depth = 0; depth < maxlog; ++depth) {
            l_pos[depth] = l;
            bool bit = (x >> (maxlog - 1 - depth)) & 1;
            l = matrix[depth].rank(bit, l) + zero_num[depth] * bit;
            r = matrix[depth].rank(bit, r) + zero_num[depth] * bit;
        }
        return r - l;
    }

    int select(T x, int k) {
        if (k == 0) return 0;
        if (rank(x, 0, length) < k) return length + 1;
        for (int depth = maxlog - 1; depth >= 0; --depth) {
            bool bit = (x >> (maxlog - 1 - depth)) & 1;
            k = matrix[depth].select(bit, l_pos[depth], k);
            k -= l_pos[depth];
        }
        return k;
    }

    int select(T x, int l, int k) {
        if (k == 0) return l;
        return select(x, k + rank(x, 0, l));
    }

    // k-th number in [l, r)
    // k : 0-indexed
    T quantile(int k, int l, int r) const {
        assert(0 <= k && k < r - l);
        T res = 0;
        for (int depth = 0; depth < maxlog; ++depth) {
            int zero = matrix[depth].rank(0, l, r);
            bool bit = k >= zero;
            l = matrix[depth].rank(bit, l) + zero_num[depth] * bit;
            r = matrix[depth].rank(bit, r) + zero_num[depth] * bit;
            res = (res << 1) | bit;
            k -= zero * bit;
        }
        return res;
    }

    tuple<int, int, int> count_3way(T x, int l, int r) const {
        int lt = 0, eq = r - l, gt = 0;
        for (int depth = 0; depth < maxlog; ++depth) {
            int tmp = r - l;
            bool bit = (x >> (maxlog - 1 - depth)) & 1;
            l = matrix[depth].rank(bit, l) + zero_num[depth] * bit;
            r = matrix[depth].rank(bit, r) + zero_num[depth] * bit;
            int d = tmp - (r - l);
            eq -= d;
            (bit ? lt : gt) += d;
        }
        return forward_as_tuple(lt, eq, gt);
    }

    // [xl, xr) * [yl, yu)
    int count(int xl, int xr, T yl, T yu) const {
        yu = min<T>(yu, (1ULL << maxlog) - 1)
        int lt_yu, lt_yl;
        tie(lt_yu, ignore, ignore) = count_3way(yu, xl, xr);
        tie(lt_yl, ignore, ignore) = count_3way(yl, xl, xr);
        return lt_yu - lt_yl;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n), nxt(n+1, n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = n-1; i >= 0; --i) {
        b[i] = nxt[a[i]];
        nxt[a[i]] = i;
    }
    // for (int i = 0; i < n; ++i) cout << b[i] << (i == n-1 ? '\n' : ' ');
    wavelet_matrix wm(b);

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        cout << wm.count(l, r, r, n+1) << '\n';
    }
}


Compiler output:
a.cc: In member function 'int wavelet_matrix<T>::count(int, int, T, T) const':
a.cc:159:9: error: expected ';' before 'int'
  159 |         int lt_yu, lt_yl;
      |         ^~~
a.cc:160:13: error: 'lt_yu' was not declared in this scope
  160 |         tie(lt_yu, ignore, ignore) = count_3way(yu, xl, xr);
      |             ^~~~~
a.cc:161:13: error: 'lt_yl' was not declared in this scope
  161 |         tie(lt_yl, ignore, ignore) = count_3way(yl, xl, xr);
      |             ^~~~~