bigint/redundant_binary_number.hpp

• View this file on GitHub
• Last update: 2024-10-12 22:46:11+09:00
• Include: #include "bigint/redundant_binary_number.hpp"
• Link: https://qoj.ac/problem/382

Depends on

• ds/fastset.hpp

Code

#include "ds/fastset.hpp"

// 2^i を足したり引いたり. k-th digit の取得.
// fastset 使用版.
// https://qoj.ac/problem/382
struct Redundant_Binary_Number_Fast {
  const int n;
  vc<char> dat;
  FastSet S;
  Redundant_Binary_Number_Fast(int n) : n(n), dat(n), S(n) {}

  int sgn() {
    int k = S.prev(n - 1);
    return (k == -1 ? 0 : dat[k]);
  }

  // k-th bit in [0,1]
  int kth(int k) {
    int j = S.prev(k - 1);
    int x = dat[k];
    int y = (j == -1 ? 0 : dat[j]);
    if (x == 0) return (y >= 0 ? 0 : 1);
    return (y >= 0 ? 1 : 0);
  }

  // 2^k * x を足す
  void add(int k, ll x) {
    while (x) {
      x += dat[k];
      dat[k] = x % 2;
      if (dat[k] == 0) {
        S.erase(k);
      } else {
        S.insert(k);
      }
      ++k, x /= 2;
    }
  }

  // 2^k を足す
  void add(int k) { add(k, 1); }
  void sub(int k) { add(k, -1); }

  string to_string() {
    string ANS;
    for (auto& x: dat) { ANS += (x == 0 ? '0' : (x == 1 ? '+' : '-')); }
    return ANS;
  }
};

// 2^i を足したり引いたり. k-th digit の取得.
template <typename KETA_TYPE = int>
struct Redundant_Binary_Number {
  using T = KETA_TYPE;
  map<T, char> dat;
  Redundant_Binary_Number() {}

  int sgn() {
    auto [k, x] = prev(infty<T>);
    return x;
  }

  // k-th bit in [0,1]
  int kth(T k) {
    int x = (dat.count(k) ? dat[k] : 0);
    int y = prev(k - 1).se;
    if (x == 0) return (y >= 0 ? 0 : 1);
    return (y >= 0 ? 1 : 0);
  }

  // 2^k * x を足す
  void add(T k, ll x) {
    while (x) {
      x += dat[k];
      if (x % 2 == 0) {
        dat.erase(k);
      } else {
        dat[k] = x % 2;
      }
      ++k, x /= 2;
    }
  }

  // 2^k を足す
  void add(T k) { add_inner(k, 1); }
  void sub(T k) { add_inner(k, -1); }

private:
  pair<T, char> prev(T k) {
    while (1) {
      auto it = dat.upper_bound(k);
      if (it == dat.begin()) return {-1, 0};
      it = ::prev(it);
      return *it;
    }
  }
};

#line 2 "ds/fastset.hpp"

// 64-ary tree

// space: (N/63) * u64

struct FastSet {
  static constexpr u32 B = 64;
  int n, log;
  vvc<u64> seg;

  FastSet() {}
  FastSet(int n) { build(n); }

  int size() { return n; }

  template <typename F>
  FastSet(int n, F f) {
    build(n, f);
  }

  void build(int m) {
    seg.clear();
    n = m;
    do {
      seg.push_back(vc<u64>((m + B - 1) / B));
      m = (m + B - 1) / B;
    } while (m > 1);
    log = len(seg);
  }
  template <typename F>
  void build(int n, F f) {
    build(n);
    FOR(i, n) { seg[0][i / B] |= u64(f(i)) << (i % B); }
    FOR(h, log - 1) {
      FOR(i, len(seg[h])) {
        seg[h + 1][i / B] |= u64(bool(seg[h][i])) << (i % B);
      }
    }
  }

  bool operator[](int i) const { return seg[0][i / B] >> (i % B) & 1; }
  void insert(int i) {
    for (int h = 0; h < log; h++) {
      seg[h][i / B] |= u64(1) << (i % B), i /= B;
    }
  }
  void add(int i) { insert(i); }
  void erase(int i) {
    u64 x = 0;
    for (int h = 0; h < log; h++) {
      seg[h][i / B] &= ~(u64(1) << (i % B));
      seg[h][i / B] |= x << (i % B);
      x = bool(seg[h][i / B]);
      i /= B;
    }
  }
  void remove(int i) { erase(i); }

  // min[x,n) or n

  int next(int i) {
    assert(i <= n);
    chmax(i, 0);
    for (int h = 0; h < log; h++) {
      if (i / B == seg[h].size()) break;
      u64 d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      i += lowbit(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += lowbit(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }

  // max [0,x], or -1

  int prev(int i) {
    assert(i >= -1);
    if (i >= n) i = n - 1;
    for (int h = 0; h < log; h++) {
      if (i == -1) break;
      u64 d = seg[h][i / B] << (63 - i % B);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      i -= __builtin_clzll(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += topbit(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }

  bool any(int l, int r) { return next(l) < r; }

  // [l, r)

  template <typename F>
  void enumerate(int l, int r, F f) {
    for (int x = next(l); x < r; x = next(x + 1)) f(x);
  }

  string to_string() {
    string s(n, '?');
    for (int i = 0; i < n; ++i) s[i] = ((*this)[i] ? '1' : '0');
    return s;
  }
};
#line 2 "bigint/redundant_binary_number.hpp"

// 2^i を足したり引いたり. k-th digit の取得.
// fastset 使用版.
// https://qoj.ac/problem/382
struct Redundant_Binary_Number_Fast {
  const int n;
  vc<char> dat;
  FastSet S;
  Redundant_Binary_Number_Fast(int n) : n(n), dat(n), S(n) {}

  int sgn() {
    int k = S.prev(n - 1);
    return (k == -1 ? 0 : dat[k]);
  }

  // k-th bit in [0,1]
  int kth(int k) {
    int j = S.prev(k - 1);
    int x = dat[k];
    int y = (j == -1 ? 0 : dat[j]);
    if (x == 0) return (y >= 0 ? 0 : 1);
    return (y >= 0 ? 1 : 0);
  }

  // 2^k * x を足す
  void add(int k, ll x) {
    while (x) {
      x += dat[k];
      dat[k] = x % 2;
      if (dat[k] == 0) {
        S.erase(k);
      } else {
        S.insert(k);
      }
      ++k, x /= 2;
    }
  }

  // 2^k を足す
  void add(int k) { add(k, 1); }
  void sub(int k) { add(k, -1); }

  string to_string() {
    string ANS;
    for (auto& x: dat) { ANS += (x == 0 ? '0' : (x == 1 ? '+' : '-')); }
    return ANS;
  }
};

// 2^i を足したり引いたり. k-th digit の取得.
template <typename KETA_TYPE = int>
struct Redundant_Binary_Number {
  using T = KETA_TYPE;
  map<T, char> dat;
  Redundant_Binary_Number() {}

  int sgn() {
    auto [k, x] = prev(infty<T>);
    return x;
  }

  // k-th bit in [0,1]
  int kth(T k) {
    int x = (dat.count(k) ? dat[k] : 0);
    int y = prev(k - 1).se;
    if (x == 0) return (y >= 0 ? 0 : 1);
    return (y >= 0 ? 1 : 0);
  }

  // 2^k * x を足す
  void add(T k, ll x) {
    while (x) {
      x += dat[k];
      if (x % 2 == 0) {
        dat.erase(k);
      } else {
        dat[k] = x % 2;
      }
      ++k, x /= 2;
    }
  }

  // 2^k を足す
  void add(T k) { add_inner(k, 1); }
  void sub(T k) { add_inner(k, -1); }

private:
  pair<T, char> prev(T k) {
    while (1) {
      auto it = dat.upper_bound(k);
      if (it == dat.begin()) return {-1, 0};
      it = ::prev(it);
      return *it;
    }
  }
};

Back to top page