Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/Library

:heavy_check_mark: test/data_structure/Static_Range_Frequency.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_frequency"

#include <cstdint>
#include <iostream>
#include <vector>

#include "../../data_structure/WaveletMatrix.hpp"

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto &val : a) {
        std::cin >> val;
    }
    ebi::WaveletMatrix<int> wm(a);
    while (q--) {
        int l, r, x;
        std::cin >> l >> r >> x;
        if (l == r) {
            std::cout << "0\n";
            continue;
        }
        std::cout << wm.rank(r, x) - wm.rank(l, x) << '\n';
    }
    return 0;
}
#line 1 "test/data_structure/Static_Range_Frequency.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_frequency"

#include <cstdint>
#include <iostream>
#include <vector>

#line 2 "data_structure/WaveletMatrix.hpp"

#line 2 "data_structure/bitVector.hpp"

#line 2 "template/int_alias.hpp"

#line 4 "template/int_alias.hpp"

namespace ebi {

using ld = long double;
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace ebi
#line 4 "data_structure/bitVector.hpp"

/*
    reference: https://misteer.hatenablog.com/entry/bit-vector
*/

#line 10 "data_structure/bitVector.hpp"

namespace ebi {

struct bitVector {
    u32 length, cn, bn;
    static u32 cw,
        bw;  // chunk, block の長さ cw = (lg N)^2, bw = (lg N)/2 とする.

    std::vector<u16> bit;
    std::vector<u32> chunk;
    std::vector<std::vector<u16>> blocks;

    bitVector(int n) : length(n) {
        cn = (length + cw - 1) / cw;
        bn = cw / bw;
        bit.assign(cn * bn, 0);
        chunk.assign(cn + 1, 0);
        blocks.assign(cn, std::vector<u16>(bn, 0));
    }

    void set(int k, int b) {
        u32 i = k / bw;
        u32 j = k % bw;
        if (b == 0) {
            bit[i] &= ~(1 << j);
        } else if (b == 1) {
            bit[i] |= (1 << j);
        }
    }

    int access(int k) {
        u32 i = k / bw;
        u32 j = k % bw;
        return bit[i] >> j & 1;
    }

    void build() {
        chunk[0] = 0;
        for (u32 i = 0; i < cn; i++) {
            blocks[i][0] = 0;
            for (u32 j = 0; j < bn - 1; j++) {
                blocks[i][j + 1] =
                    blocks[i][j] + __builtin_popcount(bit[i * bn + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bn - 1] +
                           __builtin_popcount(bit[(i + 1) * bn - 1]);
        }
    }

    // [0, r)に存在する1の数をO(1)で計算する.

    int rank(int r) {
        u32 i = r / cw;
        u32 j = (r % cw) / bw;
        u32 k = r % bw;
        u32 leftover = bit[i * bn + j] & ((1 << k) - 1);
        if (i == cn) return chunk[i];
        return chunk[i] + blocks[i][j] + __builtin_popcount(leftover);
    }

    int select(int k) {
        if (k == 0) return 0;
        if (rank(length) < k) return -1;
        u32 l = 0;
        u32 r = length;
        while (r - l > 1) {
            u32 mid = (r + l) / 2;
            if (rank(mid) >= k) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }

    int select0(int k) {
        if (k == 0) return 0;
        if (length - rank(length) < (u32)k) return -1;
        u32 l = 0;
        u32 r = length;
        while (r - l > 1) {
            u32 mid = (r + l) / 2;
            if (mid - rank(mid) >= (u32)k) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
};

u32 bitVector::cw = 1024;
u32 bitVector::bw = 16;

}  // namespace ebi
#line 4 "data_structure/WaveletMatrix.hpp"

/*
    reference: https://miti-7.hatenablog.com/entry/2018/04/28/152259
*/

#include <limits>

#include <map>

#line 12 "data_structure/WaveletMatrix.hpp"

namespace ebi {

template <class T> struct WaveletMatrix {
  private:
    int wordsize = std::numeric_limits<T>::digits;
    int n;
    std::vector<bitVector> mat;
    std::vector<int> border;
    std::map<T, int> map;

  public:
    WaveletMatrix(std::vector<T> v)
        : n(v.size()), mat(wordsize, bitVector(n)), border(wordsize) {
        for (int bit = wordsize - 1; bit >= 0; --bit) {
            std::vector<T> one, zero;
            zero.reserve(n);
            for (int i = 0; i < n; ++i) {
                if (v[i] & ((T)1 << bit)) {
                    one.emplace_back(v[i]);
                    mat[bit].set(i, 1);
                } else {
                    zero.emplace_back(v[i]);
                }
            }
            border[bit] = zero.size();
            mat[bit].build();
            std::copy(one.begin(), one.end(), std::back_inserter(zero));
            v = zero;
        }
        for (int i = 0; i < n; i++) {
            if (map[v[i]] == 0) {
                map[v[i]] = i;
            }
        }
    }

    T access(int i) {
        T val = 0;
        int k = i;
        for (int bit = wordsize - 1; bit >= 0; --bit) {
            if (mat[bit].access(k) == 1) {
                val |= ((T)1 << bit);
                k = border[bit] + mat[bit].rank(k);
            } else {
                k = k - mat[bit].rank(k);
            }
        }
        return val;
    }

    int rank(int r, T x) {
        int k = r;
        for (int bit = wordsize - 1; bit >= 0; --bit) {
            if (x & ((T)1 << bit)) {
                k = border[bit] + mat[bit].rank(k);
            } else {
                k = k - mat[bit].rank(k);
            }
        }
        return k - map[x];
    }

    int select(T x, int k) {
        k = map[x] + k;
        for (int bit = 0; bit < wordsize; ++bit) {
            if (x & ((T)1 << bit)) {
                k = mat[bit].select(k - border[bit]);
            } else {
                k = mat[bit].select0(k);
            }
        }
        return k - 1;
    }

    T quantile(int l, int r, int k) {
        T val = 0;
        for (int bit = wordsize - 1; bit >= 0; --bit) {
            int rank_l = mat[bit].rank(l);
            int rank_r = mat[bit].rank(r);
            int one = rank_r - rank_l;
            int zero = r - l - one;
            if (k <= zero) {
                l -= rank_l;
                r -= rank_r;
            } else {
                val |= (T)1 << bit;
                l = border[bit] + rank_l;
                r = border[bit] + rank_r;
                k -= zero;
            }
        }
        return val;
    }
};

}  // namespace ebi
#line 8 "test/data_structure/Static_Range_Frequency.test.cpp"

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto &val : a) {
        std::cin >> val;
    }
    ebi::WaveletMatrix<int> wm(a);
    while (q--) {
        int l, r, x;
        std::cin >> l >> r >> x;
        if (l == r) {
            std::cout << "0\n";
            continue;
        }
        std::cout << wm.rank(r, x) - wm.rank(l, x) << '\n';
    }
    return 0;
}
Back to top page