結果

問題 No.2498 OX Operations
コンテスト
ユーザー KumaTachiRen
提出日時 2023-10-05 10:10:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 307 ms / 4,000 ms
コード長 2,657 bytes
コンパイル時間 3,805 ms
コンパイル使用メモリ 254,688 KB
最終ジャッジ日時 2025-02-17 04:22:52
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

struct Fast {
  Fast() {
    std::cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(10);
  }
} fast;

#define rep(i, a, b) for (int(i) = (a); (i) < (int)(b); (i)++)
#define rrep(i, a, b) for (int(i) = (int)(b)-1; (i) >= (int)(a); (i)--)

template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
 public:
  dual_segtree(int n) {
    while (sz < n) {
      sz <<= 1;
      log++;
    }
    lz = vector<F>(sz * 2, id());
  }
  F get(int p) {
    p += sz;
    for (int i = log; i > 0; i--) push(p >> i);
    return lz[p];
  }
  void set(int p, const F& f) {
    p += sz;
    for (int i = log; i > 0; i--) push(p >> i);
    lz[p] = f;
  }
  void apply(int l, int r, const F& f) {
    if (l >= r) return;
    l += sz;
    r += sz;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    for (; l < r; l /= 2, r /= 2) {
      if (l & 1) comp(lz[l++], f);
      if (r & 1) comp(lz[--r], f);
    }
  }

 private:
  int sz = 1, log = 0;
  vector<F> lz;
  void comp(F& f, const F& g) {
    f = composition(g, f);
  }
  void push(int p) {
    comp(lz[p * 2], lz[p]);
    comp(lz[p * 2 + 1], lz[p]);
    lz[p] = id();
  }
};

const int LOG = 30;
const int MASK = (1 << LOG) - 1;
using P = pair<int, int>;
using mint = modint998244353;

P composition(P f, P g) {
  return P((~g.first & f.first) | (g.first & f.second), (~g.second & f.first) | (g.second & f.second));
};
P id() { return P(0, MASK); }

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> m(n);
  rep(i, 0, n) cin >> m[i];
  dual_segtree<P, composition, id> seg(n);

  while (q--) {
    char c;
    int l, r, x;
    cin >> c >> l >> r >> x;
    l--;
    seg.apply(l, r, c == 'o' ? P(x, MASK) : P(x, MASK ^ x));
  }

  using arr = array<mint, LOG + 1>;
  arr prod;
  prod.fill(1);
  auto solve_small = [&prod](int b, int c, int m) -> void {
    arr dp;
    int a = 0, d;
    rrep(k, 0, LOG) {
      arr newdp;
      d = (b >> k) & 1;
      rep(i, d, LOG + 1) newdp[i] += dp[i - d];
      d = (c >> k) & 1;
      rep(i, d, LOG + 1) newdp[i] += dp[i - d];
      dp = newdp;
      a += (b >> k) & 1;
      if ((m >> k) & 1) {
        dp[a] += 1;
        a += ((c >> k) & 1) - ((b >> k) & 1);
      }
    }
    rep(i, 0, LOG) dp[i + 1] += dp[i];
    rep(i, 0, LOG + 1) prod[i] *= dp[i];
  };

  rep(i, 0, n) {
    auto p = seg.get(i);
    solve_small(p.first, p.second, m[i] + 1);
  }

  mint ans = LOG * prod[LOG];
  rep(i, 0, LOG) ans -= prod[i];
  cout << ans.val() << endl;
}
0