その他/平方分割
(test/misc/sqrt_decomposition.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G

Depends on

• 平方分割 (sqrt decomposition) (include/emthrm/misc/sqrt_decomposition.hpp)

Code

/*
 * @title その他/平方分割
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
 */

#include <iostream>
#include <vector>

#include "emthrm/misc/sqrt_decomposition.hpp"

std::vector<long long> a, b, lazy;

template <typename T>
void emthrm::SqrtDecomposition::partial_update(const int idx, const T val) {
  a[idx] += val;
  b[idx / block_size] += val;
}

template <typename T>
void emthrm::SqrtDecomposition::total_update(const int idx, const T val) {
  lazy[idx] += val;
  to_be_eval[idx] = true;
}

template <typename T>
void emthrm::SqrtDecomposition::partial_query(const int idx, T* val) {
  const int block = idx / block_size;
  if (to_be_eval[block]) {
    for (int i = ls[block]; i < rs[block]; ++i) {
      partial_update(i, lazy[block]);
    }
    lazy[block] = 0;
    to_be_eval[block] = false;
  }
  *val += a[idx];
}

template <typename T>
void emthrm::SqrtDecomposition::total_query(const int idx, T* val) {
  *val += b[idx] + lazy[idx] * (rs[idx] - ls[idx]);
}

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::SqrtDecomposition sqrt_decomposition(n);
  a.assign(n, 0);
  b.assign(sqrt_decomposition.n, 0);
  lazy.assign(sqrt_decomposition.n, 0);
  while (q--) {
    int type, s, t;
    std::cin >> type >> s >> t;
    --s; --t;
    if (type == 0) {
      int x;
      std::cin >> x;
      sqrt_decomposition.update(s, t + 1, x);
    } else if (type == 1) {
      std::cout << sqrt_decomposition.query(s, t + 1, 0LL) << '\n';
    }
  }
  return 0;
}

#line 1 "test/misc/sqrt_decomposition.test.cpp"
/*
 * @title その他/平方分割
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/misc/sqrt_decomposition.hpp"



#include <cmath>
#line 6 "include/emthrm/misc/sqrt_decomposition.hpp"

namespace emthrm {

struct SqrtDecomposition {
  const int block_size, n;
  std::vector<int> ls, rs;
  std::vector<bool> to_be_eval;

  explicit SqrtDecomposition(const int n_)
      : block_size(std::round(std::sqrt(n_))),
        n((n_ + block_size - 1) / block_size) {
    ls.resize(n);
    rs.resize(n);
    to_be_eval.assign(n, false);
    for (int i = 0; i < n; ++i) {
      ls[i] = block_size * i;
      rs[i] = (i + 1 == n ? n_ : block_size * (i + 1));
    }
  }

  template <typename T> void partial_update(const int idx, const T val);

  template <typename T> void total_update(const int idx, const T val);

  template <typename T>
  void update(const int l, const int r, const T val) {
    if (r <= l) [[unlikely]] return;
    const int b_l = l / block_size, b_r = (r - 1) / block_size;
    if (b_l < b_r) {
      if (l == ls[b_l]) {
        total_update(b_l, val);
      } else {
        for (int i = l; i < rs[b_l]; ++i) {
          partial_update(i, val);
        }
      }
      for (int i = b_l + 1; i < b_r; ++i) {
        total_update(i, val);
      }
      if (r == rs[b_r]) {
        total_update(b_r, val);
      } else {
        for (int i = ls[b_r]; i < r; ++i) {
          partial_update(i, val);
        }
      }
    } else {
      for (int i = l; i < r; ++i) {
        partial_update(i, val);
      }
    }
  }

  template <typename T> void partial_query(const int idx, T* val);

  template <typename T> void total_query(const int idx, T* val);

  template <typename T>
  T query(const int l, const int r, const T id) {
    const int b_l = l / block_size, b_r = (r - 1) / block_size;
    T res = id;
    if (b_l < b_r) {
      if (l == ls[b_l]) {
        total_query(b_l, &res);
      } else {
        for (int i = l; i < rs[b_l]; ++i) {
          partial_query(i, &res);
        }
      }
      for (int i = b_l + 1; i < b_r; ++i) {
        total_query(i, &res);
      }
      if (r == rs[b_r]) {
        total_query(b_r, &res);
      } else {
        for (int i = ls[b_r]; i < r; ++i) {
          partial_query(i, &res);
        }
      }
    } else {
      for (int i = l; i < r; ++i) {
        partial_query(i, &res);
      }
    }
    return res;
  }
};

}  // namespace emthrm


#line 11 "test/misc/sqrt_decomposition.test.cpp"

std::vector<long long> a, b, lazy;

template <typename T>
void emthrm::SqrtDecomposition::partial_update(const int idx, const T val) {
  a[idx] += val;
  b[idx / block_size] += val;
}

template <typename T>
void emthrm::SqrtDecomposition::total_update(const int idx, const T val) {
  lazy[idx] += val;
  to_be_eval[idx] = true;
}

template <typename T>
void emthrm::SqrtDecomposition::partial_query(const int idx, T* val) {
  const int block = idx / block_size;
  if (to_be_eval[block]) {
    for (int i = ls[block]; i < rs[block]; ++i) {
      partial_update(i, lazy[block]);
    }
    lazy[block] = 0;
    to_be_eval[block] = false;
  }
  *val += a[idx];
}

template <typename T>
void emthrm::SqrtDecomposition::total_query(const int idx, T* val) {
  *val += b[idx] + lazy[idx] * (rs[idx] - ls[idx]);
}

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::SqrtDecomposition sqrt_decomposition(n);
  a.assign(n, 0);
  b.assign(sqrt_decomposition.n, 0);
  lazy.assign(sqrt_decomposition.n, 0);
  while (q--) {
    int type, s, t;
    std::cin >> type >> s >> t;
    --s; --t;
    if (type == 0) {
      int x;
      std::cin >> x;
      sqrt_decomposition.update(s, t + 1, x);
    } else if (type == 1) {
      std::cout << sqrt_decomposition.query(s, t + 1, 0LL) << '\n';
    }
  }
  return 0;
}

Back to top page