結果
問題 |
No.3227 Matrix Query
|
ユーザー |
|
提出日時 | 2025-08-08 22:27:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 248 ms / 8,000 ms |
コード長 | 6,420 bytes |
コンパイル時間 | 3,608 ms |
コンパイル使用メモリ | 293,184 KB |
実行使用メモリ | 16,380 KB |
最終ジャッジ日時 | 2025-08-08 22:27:44 |
合計ジャッジ時間 | 10,915 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> namespace MyLib { template<typename T> class SegmentTree { protected: std::vector<std::vector<T>> containers; const std::function<T(T, T)> pick_up; const T default_value; public: constexpr SegmentTree(const std::function<T(T, T)> pick_up, const std::vector<T>& initializer, const T default_value) : pick_up(pick_up), default_value(default_value) { containers.clear(); if (initializer.size() == 0) return; else if (initializer.size() == 1) { containers.emplace_back(1, initializer[0]); return; } uint_fast32_t l = 0, r = 30; while (l + 1 < r) { const auto c = (l + r) >> 1; if (((uint_fast32_t)1 << c) < initializer.size()) l = c; else r = c; } containers.emplace_back((uint_fast32_t)1 << r); uint_fast32_t i; for (i = 0; i != initializer.size(); ++i) containers[0][i] = initializer[i]; for (; i != ((uint_fast32_t)1 << r); ++i) containers[0][i] = default_value; for (--r; r != 0; --r) { containers.emplace_back((uint_fast32_t)1 << r); for (i = 0; i != ((uint_fast32_t)1 << r); ++i) containers[containers.size() - 1][i] = pick_up(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]); } containers.emplace_back(1, pick_up(containers[containers.size() - 1][0], containers[containers.size() - 1][1])); } constexpr SegmentTree(const std::function<T(T, T)> pick_up, std::vector<T>&& initializer, const T default_value) : pick_up(pick_up), default_value(default_value) { containers.clear(); if (initializer.size() == 0) return; uint_fast32_t l = 0, r = 30; while (l + 1 < r) { const auto c = (l + r) >> 1; if (((uint_fast32_t)1 << c) < initializer.size()) l = c; else r = c; } containers.emplace_back(std::move(initializer)); containers[0].resize((uint_fast32_t)1 << r, default_value); uint_fast32_t i; for (--r; r != 0; --r) { containers.emplace_back((uint_fast32_t)1 << r); for (i = 0; i != ((uint_fast32_t)1 << r); ++i) containers[containers.size() - 1][i] = pick_up(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]); } containers.emplace_back(1, pick_up(containers[containers.size() - 1][0], containers[containers.size() - 1][1])); } constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; } constexpr uint_fast32_t size() const noexcept { return containers[0].size(); } constexpr uint_fast32_t layer() const noexcept { return containers.size(); } constexpr T update(uint_fast32_t index, const T value) noexcept { containers[0][index] = value; index >>= 1; for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1) containers[i][index] = pick_up(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]); return value; } constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept { if (containers.size() == 0 || end_index > containers[0].size()) return default_value; T ret_l = default_value, ret_r = default_value; for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer) { if (first_index & 1) ret_l = pick_up(ret_l, containers[cur_layer][first_index]), ++first_index; if (end_index & 1) ret_r = pick_up(containers[cur_layer][end_index - 1], ret_r); } return pick_up(ret_l, ret_r); } }; } static inline constexpr std::array<std::array<uint_fast32_t, 2>, 2> mul(const std::array<std::array<uint_fast32_t, 2>, 2>& a, const std::array<std::array<uint_fast32_t, 2>, 2>& b, const uint_fast32_t K) noexcept { std::array<std::array<uint_fast32_t, 2>, 2> result = { { 0, }, }; for (uint_fast32_t i = 0; i != 2; ++i) for (uint_fast32_t j = 0; j != 2; ++j) result[i][j] = (static_cast<uint_fast64_t>(a[i][0]) * b[0][j] + static_cast<uint_fast64_t>(a[i][1]) * b[1][j]) % K; return result; } static inline constexpr std::vector<std::array<std::array<uint_fast32_t, 2>, 2>> prepare(const uint_fast32_t N, const std::vector<std::array<std::array<int_fast32_t, 2>, 2>>& M, const uint_fast32_t K) noexcept { std::vector<std::array<std::array<uint_fast32_t, 2>, 2>> new_M(N); for (uint_fast32_t i = 0; i != N; ++i) for (uint_fast32_t j = 0; j != 2; ++j) for (uint_fast32_t k = 0; k != 2; ++k) new_M[i][j][k] = (M[i][j][k] + K * UINT64_C(50'000'000)) % K; return new_M; } static inline constexpr std::vector<std::array<std::array<uint_fast32_t, 2>, 2>> solve(const uint_fast32_t N, const uint_fast32_t Q, const uint_fast32_t K, std::vector<std::array<std::array<uint_fast32_t, 2>, 2>>&& A, const std::vector<uint_fast32_t>& index, const std::vector<uint_fast32_t>& L, const std::vector<uint_fast32_t>& R, const std::vector<std::array<std::array<uint_fast32_t, 2>, 2>>& Y) noexcept { std::vector<std::array<std::array<uint_fast32_t, 2>, 2>> ans(Q); MyLib::SegmentTree<std::array<std::array<uint_fast32_t, 2>, 2>> st([K](const std::array<std::array<uint_fast32_t, 2>, 2>& a, const std::array<std::array<uint_fast32_t, 2>, 2>& b) constexpr noexcept { return mul(a, b, K); }, std::move(A), std::array<std::array<uint_fast32_t, 2>, 2>{ std::array<uint_fast32_t, 2>{ 1, 0 }, std::array<uint_fast32_t, 2>{ 0, 1 } }); for (uint_fast32_t i = 0; i != Q; ++i) st.update(index[i] - 1, Y[i]), ans[i] = st.range_pick_up(L[i] - 1, R[i]); return ans; } static inline void output(const uint_fast32_t Q, const std::vector<std::array<std::array<uint_fast32_t, 2>, 2>>& ans) noexcept { for (uint_fast32_t i = 0; i != Q; ++i) for (uint_fast32_t j = 0; j != 2; ++j) std::cout << ans[i][j][0] << ' ' << ans[i][j][1] << '\n'; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t K, N, Q, i, j, k; std::cin >> K >> N; std::vector<std::array<std::array<int_fast32_t, 2>, 2>> A(N); for (i = 0; i != N; ++i) for (j = 0; j != 2; ++j) for (k = 0; k != 2; ++k) std::cin >> A[i][j][k]; std::cin >> Q; std::vector<uint_fast32_t> index(Q), L(Q), R(Q); std::vector<std::array<std::array<int_fast32_t, 2>, 2>> Y(Q); for (i = 0; i != Q; ++i) { std::cin >> index[i] >> L[i] >> R[i]; for (j = 0; j != 2; ++j) for (k = 0; k != 2; ++k) std::cin >> Y[i][j][k]; } output(Q, solve(N, Q, K, prepare(N, A, K), index, L, R, prepare(Q, Y, K))); return 0; }