test/ds/fenwick2d.test.cpp

View this file on GitHub
Last update: 2024-11-09 00:49:07+00:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842

Depends on

Code

// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842

#include "prelude.hpp"
#include "ds/fenwick2d.hpp"

int h, w, T, q;
tuple<int, int, int> trans[100000], *l = trans, *r = trans;

int main() {
  scanf("%d%d%d%d", &h, &w, &T, &q);
  fenwick_tree_2d<addition<int>> a(h, w), b(h, w);
  while (q--) {
    int t, c, i, j; scanf("%d%d%d%d", &t, &c, &i, &j);
    i--, j--;
    while (l != r && get<0>(*l) <= t) {
      auto [x, s, T] = *l++;
      a.sub(s, T, 1);
      b.add(s, T, 1);
    }
    if (c == 0) {
      a.add(i, j, 1);
      *r++ = {t+T, i, j};
    } else if (c == 1) {
      b.assign(i, j, 0);
    } else {
      int i2, j2; scanf("%d%d", &i2, &j2);
      printf("%d %d\n", b.sum(i, j, i2, j2), a.sum(i, j, i2, j2));
    }
  }
}

#line 1 "test/ds/fenwick2d.test.cpp"
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "algebra.hpp"

#define CONST(val) [=] { return val; }
#define WRAP_FN(func) \
  [](auto&&... args) { return func(forward<decltype(args)>(args)...); }

template <class Unit, class Op>
struct monoid : private Unit, private Op {
  using type = decltype(declval<Unit>()());
  monoid(Unit unit, Op op) : Unit(unit), Op(op) {}
  type unit() const { return Unit::operator()(); }
  type op(type a, type b) const { return Op::operator()(a, b); }
};

template <class Unit, class Op, class Inv>
struct group : monoid<Unit, Op>, private Inv {
  using type = typename monoid<Unit, Op>::type;
  group(Unit unit, Op op, Inv inv) : monoid<Unit, Op>(unit, op), Inv(inv) {}
  type inv(type a) const { return Inv::operator()(a); }
};

template <class T>
struct addition {
  using type = T;
  type unit() const { return 0; }
  type op(type a, type b) const { return a + b; }
  type inv(type a) const { return -a; }
};

template <class T>
struct maximum {
  using type = T;
  type unit() const { return numeric_limits<T>::min(); }
  type op(type a, type b) const { return a > b ? a : b; }
};

template <class T>
struct minimum {
  using type = T;
  type unit() const { return numeric_limits<T>::max(); }
  type op(type a, type b) const { return a > b ? b : a; }
};

template <class T, T nul = -1>
struct assign {
  using type = T;
  type unit() const { return nul; }
  type op(type a, type b) const { return b == nul ? a : b; }
};
#line 3 "bit/clz.hpp"

#pragma GCC target("lzcnt")

template <class T>
int clz(T x) {
    if (!x) return sizeof(T) * 8;
    if constexpr (sizeof(T) <= sizeof(unsigned)) {
        return __builtin_clz((unsigned)x);
    } else if constexpr (sizeof(T) <= sizeof(unsigned long long)) {
        return __builtin_clzll((unsigned long long)x);
    } else if constexpr (sizeof(T) <= sizeof(unsigned long long) * 2) {
        int l = clz((unsigned long long)(x >> sizeof(unsigned long long) * 8));
        return l != sizeof(unsigned long long) * 8 ? l : l + clz((unsigned long long)x);
    }
}
#line 4 "bit/ilog2.hpp"

template <class T>
__attribute__((pure)) int ilog2(T x) { assert(x != 0); return sizeof(T) * 8 - 1 - clz(x); }

template <class T>
__attribute__((pure)) int ilog2_ceil(T x) { return x == 0 || x == 1 ? 0 : ilog2(x - 1) + 1; }

template <class T, enable_if_t<is_signed_v<T>>* = nullptr>
__attribute__((pure)) T bit_floor(T x) { return T(1) << ilog2(x); }

template <class T, enable_if_t<is_signed_v<T>>* = nullptr>
__attribute__((pure)) T bit_ceil(T x) { return T(1) << ilog2_ceil(x); }
#line 4 "ds/fenwick2d.hpp"

template <class M>
class fenwick_tree_2d {
 public:
  using value_type = typename M::type;
  fenwick_tree_2d(vector<vector<value_type>> v, M m = M())
      : m(m), data(move(v)) {
    rep(i, data.size()) data[i].insert(data.cbegin(), m.unit());
    data.insert(data.begin(), vector<value_type>(data[0].size(), m.unit()));
    rep(i, data.size()) {
      for (int j = 1; j < data[i].size(); j++) {
        if (j + lsb(j) < data[i].size()) {
          data[i][j + lsb(j)] = m.op(data[i][j + lsb(j)], data[i][j]);
        }
      }
    }
    for (int i = 1; i < data.size(); i++) {
      if (i + lsb(i) < data.size()) {
        rep(j, data[i].size()) {
          data[i + lsb(i)][j] = m.op(data[i + lsb(i)][j], data[i][j]);
        }
      }
    }
  }
  template <class Iter>
  fenwick_tree_2d(Iter f, Iter l, M m = M())
      : fenwick_tree_2d(vector<value_type>(f, l), m) {}
  fenwick_tree_2d(int n0, int n1, M m = M())
      : m(m), data(n0 + 1, vector<value_type>(n1 + 1, m.unit())) {}
  int size() const { return data.size() - 1; }
  void clear() {
    rep(i, data.size()) fill(data[i].begin(), data[i].end(), m.unit());
  }
  void add(int i0, int j0, value_type v) {
    for (int i = i0 + 1; i < data.size(); i += lsb(i))
      for (int j = j0 + 1; j < data[i].size(); j += lsb(j))
        data[i][j] = m.op(data[i][j], v);
  }
  void sub(int i, int j, value_type v) { add(i, j, m.inv(v)); }
  void assign(int i, int j, value_type v) {
    add(i, j, m.op(v, m.inv(sum(i, j, i + 1, j + 1))));
  }
  value_type sum(int ri, int rj) const {
    value_type res = m.unit();
    for (int i = ri; i; i -= lsb(i)) {
      for (int j = rj; j; j -= lsb(j)) {
        res = m.op(res, data[i][j]);
      }
    }
    return res;
  }
  value_type sum(int li, int lj, int ri, int rj) const {
    return m.op(m.op(sum(li, lj), sum(ri, rj)),
                m.inv(m.op(sum(li, rj), sum(ri, lj))));
  }

 private:
  M m;
  vector<vector<value_type>> data;
  static int lsb(int a) { return a & -a; }
};
#line 5 "test/ds/fenwick2d.test.cpp"

int h, w, T, q;
tuple<int, int, int> trans[100000], *l = trans, *r = trans;

int main() {
  scanf("%d%d%d%d", &h, &w, &T, &q);
  fenwick_tree_2d<addition<int>> a(h, w), b(h, w);
  while (q--) {
    int t, c, i, j; scanf("%d%d%d%d", &t, &c, &i, &j);
    i--, j--;
    while (l != r && get<0>(*l) <= t) {
      auto [x, s, T] = *l++;
      a.sub(s, T, 1);
      b.add(s, T, 1);
    }
    if (c == 0) {
      a.add(i, j, 1);
      *r++ = {t+T, i, j};
    } else if (c == 1) {
      b.assign(i, j, 0);
    } else {
      int i2, j2; scanf("%d%d", &i2, &j2);
      printf("%d %d\n", b.sum(i, j, i2, j2), a.sum(i, j, i2, j2));
    }
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-12	00_sample_00.in	AC	13 ms	8 MB
g++-12	10_small_rand_00.in	AC	13 ms	8 MB
g++-12	11_middle_rand_00.in	AC	13 ms	8 MB
g++-12	12_large_rand_00.in	AC	19 ms	10 MB
g++-12	13_max_rand_00.in	AC	275 ms	54 MB
g++-12	14_spanshort_rand_00.in	AC	324 ms	54 MB
g++-12	20_small_addonly_00.in	AC	13 ms	8 MB
g++-12	21_middle_addonly_00.in	AC	14 ms	8 MB
g++-12	22_large_addonly_00.in	AC	50 ms	12 MB
g++-12	23_max_addonly_00.in	AC	142 ms	54 MB
g++-12	24_spanshort_addonly_00.in	AC	270 ms	54 MB
g++-12	30_small_eatonly_00.in	AC	13 ms	8 MB
g++-12	31_middle_eatonly_00.in	AC	13 ms	8 MB
g++-12	32_large_eatonly_00.in	AC	75 ms	16 MB
g++-12	33_max_eatonly_00.in	AC	212 ms	53 MB
g++-12	34_spanshort_eatonly_00.in	AC	220 ms	53 MB
g++-12	40_small_queonly_00.in	AC	13 ms	8 MB
g++-12	41_middle_queonly_00.in	AC	14 ms	8 MB
g++-12	42_large_queonly_00.in	AC	131 ms	22 MB
g++-12	43_max_queonly_00.in	AC	444 ms	53 MB
g++-12	44_spanshort_queonly_00.in	AC	442 ms	53 MB
g++-12	50_small_noadd_00.in	AC	13 ms	8 MB
g++-12	51_middle_noadd_00.in	AC	14 ms	8 MB
g++-12	52_large_noadd_00.in	AC	31 ms	9 MB
g++-12	53_max_noadd_00.in	AC	350 ms	53 MB
g++-12	54_spanshort_noadd_00.in	AC	347 ms	53 MB
g++-12	60_small_noeat_00.in	AC	13 ms	8 MB
g++-12	61_middle_noeat_00.in	AC	13 ms	8 MB
g++-12	62_large_noeat_00.in	AC	84 ms	36 MB
g++-12	63_max_noeat_00.in	AC	304 ms	54 MB
g++-12	64_spanshort_noeat_00.in	AC	355 ms	54 MB
g++-12	70_small_noque_00.in	AC	14 ms	8 MB
g++-12	71_middle_noque_00.in	AC	14 ms	8 MB
g++-12	72_large_noque_00.in	AC	34 ms	14 MB
g++-12	73_max_noque_00.in	AC	200 ms	54 MB
g++-12	74_spanshort_noque_00.in	AC	260 ms	54 MB
g++-12	80_small_flrange_00.in	AC	13 ms	8 MB
g++-12	81_middle_flrange_00.in	AC	14 ms	8 MB
g++-12	82_large_flrange_00.in	AC	47 ms	39 MB
g++-12	83_max_flrange_00.in	AC	186 ms	54 MB
g++-12	84_spanshort_flrange_00.in	AC	225 ms	54 MB
g++-12	90_challenge_00.in	AC	141 ms	53 MB
g++-12	90_challenge_01.in	AC	141 ms	53 MB
g++-12	90_challenge_02.in	AC	139 ms	53 MB