結果
| 問題 | No.2265 Xor Range Substring Sum Query |
| ユーザー |
 sotanishy
|
| 提出日時 | 2023-03-09 18:23:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,173 ms / 5,000 ms |
| コード長 | 5,511 bytes |
| コンパイル時間 | 2,499 ms |
| コンパイル使用メモリ | 208,024 KB |
| 最終ジャッジ日時 | 2025-02-11 07:12:42 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)#define all(x) begin(x), end(x)template <typename T>bool chmax(T& a, const T& b) {return a < b ? (a = b, 1) : 0;}template <typename T>bool chmin(T& a, const T& b) {return a > b ? (a = b, 1) : 0;}template <int mod>class Modint {using mint = Modint;static_assert(mod > 0, "Modulus must be positive");public:static constexpr int get_mod() noexcept { return mod; }constexpr Modint(long long y = 0) noexcept: x(y >= 0 ? y % mod : (y % mod + mod) % mod) {}constexpr int value() const noexcept { return x; }constexpr mint& operator+=(const mint& r) noexcept {if ((x += r.x) >= mod) x -= mod;return *this;}constexpr mint& operator-=(const mint& r) noexcept {if ((x += mod - r.x) >= mod) x -= mod;return *this;}constexpr mint& operator*=(const mint& r) noexcept {x = static_cast<int>(1LL * x * r.x % mod);return *this;}constexpr mint& operator/=(const mint& r) noexcept {*this *= r.inv();return *this;}constexpr mint operator-() const noexcept { return mint(-x); }constexpr mint operator+(const mint& r) const noexcept {return mint(*this) += r;}constexpr mint operator-(const mint& r) const noexcept {return mint(*this) -= r;}constexpr mint operator*(const mint& r) const noexcept {return mint(*this) *= r;}constexpr mint operator/(const mint& r) const noexcept {return mint(*this) /= r;}constexpr bool operator==(const mint& r) const noexcept { return x == r.x; }constexpr bool operator!=(const mint& r) const noexcept { return x != r.x; }constexpr mint inv() const noexcept {int a = x, b = mod, u = 1, v = 0;while (b > 0) {int t = a / b;std::swap(a -= t * b, b);std::swap(u -= t * v, v);}return mint(u);}constexpr mint pow(long long n) const noexcept {mint ret(1), mul(x);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend std::ostream& operator<<(std::ostream& os, const mint& r) {return os << r.x;}friend std::istream& operator>>(std::istream& is, mint& r) {long long t;is >> t;r = mint(t);return is;}private:int x;};template <typename M>class XorSegmentTree {using T = typename M::T;public:XorSegmentTree() = default;explicit XorSegmentTree(int n): XorSegmentTree(std::vector<T>(n, M::id())) {}explicit XorSegmentTree(const std::vector<T>& v) {n = 0, size = 1;while (size < (int)v.size()) size <<= 1, ++n;table.resize(2 * size);for (int k = 0; k < size; ++k) {table[size + k].resize(1, k < (int)v.size() ? v[k] : M::id());}half = 1 << ((n + 1) / 2);for (int k = size - 1; k >= half; --k) pull(k);}void update(int k, const T& x) {k += size;table[k][0] = x;for (k >>= 1; k >= half; k >>= 1) pull(k);}T fold(int l, int r, int x) const {T vl = M::id(), vr = M::id();int i = 0;for (l += size, r += size; l < r && l > 2 * half;l >>= 1, r >>= 1, ++i) {if (l & 1)vl = M::op(vl, table[l++ ^ (x >> i)][x & ((1 << i) - 1)]);if (r & 1)vr = M::op(table[--r ^ (x >> i)][x & ((1 << i) - 1)], vr);}for (int k = l; k < r; ++k) {vl = M::op(vl, table[k ^ (x >> i)][x & ((1 << i) - 1)]);}return M::op(vl, vr);}private:int n, size, half;std::vector<std::vector<T>> table;void pull(int k) {int i = n - (31 - __builtin_clz(k));table[k].resize(1 << i);for (int x = 0; x < (1 << i); ++x) {T vl = table[2 * k][x & ~(1 << (i - 1))];T vr = table[2 * k + 1][x & ~(1 << (i - 1))];if (x >> (i - 1) & 1) std::swap(vl, vr);table[k][x] = M::op(vl, vr);}}};using mint = Modint<998244353>;vector<mint> pow11, pow2;struct Monoid {using T = pair<mint, int>;static T id() { return {0, 0}; }static T op(T a, T b) {auto [xa, na] = a;auto [xb, nb] = b;return {xa * pow11[nb] + xb * pow2[na], na + nb};}};int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);int n;cin >> n;string s;cin >> s;pow11.resize((1 << n) + 1, 1);pow2.resize((1 << n) + 1, 1);rep(i, 1, (1 << n) + 1) {pow11[i] = pow11[i - 1] * 11;pow2[i] = pow2[i - 1] * 2;}vector<pair<mint, int>> init(1 << n);rep(i, 0, 1 << n) { init[i] = {s[i] - '0', 1}; }XorSegmentTree<Monoid> st(init);int q;cin >> q;while (q--) {int t;cin >> t;if (t == 1) {int x, y;cin >> x >> y;st.update(x, {y, 1});} else {int l, r, x;cin >> l >> r >> x;++r;cout << st.fold(l, r, x).first << "\n";}}}