結果

問題 No.2611 Count 01
コンテスト
ユーザー Yaowei Lyu
提出日時 2024-01-19 23:16:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 353 ms / 6,000 ms
コード長 2,318 bytes
コンパイル時間 4,671 ms
コンパイル使用メモリ 250,784 KB
実行使用メモリ 41,072 KB
最終ジャッジ日時 2024-09-28 05:05:58
合計ジャッジ時間 13,108 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#ifndef ONLINE_JUDGE
#include "debug.h"  // https://github.com/Heltion/debug.h/blob/main/debug.h
#else
#define debug(...) (void)417
#endif
constexpr i64 mod = 998244353;
struct Node {
  i64 clr, cl, cr, c, c0, c1, s0, s1;
  Node operator*(const Node& rhs) const {
    return {
        (clr + rhs.clr + mod - c0 * rhs.c1 % mod + mod - c1 * rhs.c0 % mod) %
            mod,
        (cl + rhs.cl + c0 * rhs.s1 % mod + c1 * rhs.s0 % mod) % mod,
        (cr + rhs.cr + s0 * rhs.c1 % mod + s1 * rhs.c0 % mod) % mod,
        (c + rhs.c + mod - s0 * rhs.s1 % mod + mod - s1 * rhs.s0 % mod) %
            mod,
        c0 + rhs.c0,
        c1 + rhs.c1,
        (s0 + rhs.s0) % mod,
        (s1 + rhs.s1) % mod,
    };
  }
};
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  s = " " + s;
  vector<Node> nodes(n << 2);
  auto update = [&](int i) {
    auto rec = [&](auto& rec, int p, int tl, int tr) -> void {
      if (tl == tr) {
        if (s[i] == '0') { nodes[p] = {0, 0, 0, 0, 1, 0, i, 0}; };
        if (s[i] == '1') { nodes[p] = {0, 0, 0, 0, 0, 1, 0, i}; };
        return;
      }
      int tm = midpoint(tl, tr);
      if (i <= tm) { rec(rec, p * 2, tl, tm); }
      if (i > tm) { rec(rec, p * 2 + 1, tm + 1, tr); }
      nodes[p] = nodes[p * 2] * nodes[p * 2 + 1];
    };
    rec(rec, 1, 1, n);
  };
  auto query = [&](int l, int r) {
    auto rec = [&](auto& rec, int p, int tl, int tr) -> Node {
      if (tl >= l and tr <= r) { return nodes[p]; }
      int tm = midpoint(tl, tr);
      if (r <= tm) { return rec(rec, p * 2, tl, tm); }
      if (l > tm) { return rec(rec, p * 2 + 1, tm + 1, tr); }
      return rec(rec, p * 2, tl, tm) * rec(rec, p * 2 + 1, tm + 1, tr);
    };
    return rec(rec, 1, 1, n);
  };
  for (int i = 1; i <= n; i += 1) { update(i); }
  for (int qi = 0, op, i, l, r; qi < q; qi += 1) {
    cin >> op;
    if (op == 1) {
      cin >> i;
      s[i] ^= 1;
      update(i);
    } else {
      cin >> l >> r;
      auto node = query(l, r);
      cout << (node.clr * (l - 1) % mod * (r + 1) % mod +
               node.cl * (l - 1) % mod + node.cr * (r + 1) % mod + node.c) %
                  mod
           << "\n";
    }
  }
}
0