結果
問題 | No.2498 OX Operations |
ユーザー |
![]() |
提出日時 | 2023-10-07 00:48:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,011 ms / 4,000 ms |
コード長 | 3,956 bytes |
コンパイル時間 | 3,449 ms |
コンパイル使用メモリ | 280,000 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-26 17:38:24 |
合計ジャッジ時間 | 25,166 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using mint = modint998244353;template <class F, F (*composition)(F, F), F (*id)()> struct dual_segtree {public:dual_segtree() : dual_segtree(0) {}explicit dual_segtree(int n) : dual_segtree(std::vector<F>(n, id())) {}explicit dual_segtree(const std::vector<F>& v) : _n(int(v.size())) {auto ceil_log2 = [](int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;};log = ceil_log2(_n);size = 1 << log;lz = std::vector<F>(2 * size, id());for (int i = 0; i < _n; i++) lz[size + i] = v[i];}void set(int p, F x) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);lz[p] = x;}F get(int p) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);return lz[p];}void apply(int p, F f) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);lz[p] = composition(f, lz[p]);}void apply(int l, int r, F f) {assert(0 <= l && l <= r && r <= _n);if (l == r) return;l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}while (l < r) {if (l & 1) all_apply(l++, f);if (r & 1) all_apply(--r, f);l >>= 1;r >>= 1;}}void push_all() {for (int i = 1; i < size; i++) push(i);}F get_raw(int p) {assert(0 <= p && p < _n);return lz[size + p];}private:int _n, size, log;std::vector<F> lz;void all_apply(int k, F f) {lz[k] = composition(f, lz[k]);}void push(int k) {all_apply(2 * k, lz[k]);all_apply(2 * k + 1, lz[k]);lz[k] = id();}};struct F {int a, b;};F compositon(F f, F g) {// fa(gax + gb) + fbreturn {f.a & g.a, (f.a & g.b) ^ f.b};}F id() {return {~0, 0};}} int main() {ios::sync_with_stdio(false);cin.tie(0);int n, q;cin >> n >> q;VI m(n);rep(i, n) cin >> m[i];dual_segtree<F, compositon, id> seg(n);rep(_, q) {char c;int l, r, x;cin >> c >> l >> r >> x;l--;if (c == 'o') seg.apply(l, r, {~x, x});else seg.apply(l, r, {~0, x});}vector<mint> cnt(31, 1);rep(i, n) {auto [a, b] = seg.get(i);int x = b, y = a ^ b;mint f[2][31];f[0][0] = 1;int k = m[i];rep(_, 31) {mint g[2][2];g[0][x & 1] = 1;g[1][y & 1] = 1;mint nf[4][31];rep(i, 2) rep(j, 31) rep(p, 2) rep(q, 2) {nf[i+p][j+q] += f[i][j] * g[p][q];}rrep(i, 3) rep(j, 31) nf[i+1][j] += nf[i][j];rep(i, 4) if ((i & 1) == (k & 1)) rep(j, 31) {f[i >> 1][j] = nf[i][j];}x >>= 1, y >>= 1, k >>= 1;}rep(j, 30) f[0][j+1] += f[0][j];rep(j, 31) cnt[j] *= f[0][j];}rrep(j, 30) cnt[j+1] -= cnt[j];mint ans;rep(j, 31) ans += j * cnt[j];cout << ans.val() << '\n';}