結果

問題 No.2611 Count 01
ユーザー Yaowei LyuYaowei Lyu
提出日時 2024-01-19 23:16:57
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 340 ms
40,956 KB
testcase_04 AC 324 ms
40,940 KB
testcase_05 AC 317 ms
41,020 KB
testcase_06 AC 351 ms
40,940 KB
testcase_07 AC 321 ms
40,836 KB
testcase_08 AC 325 ms
40,828 KB
testcase_09 AC 337 ms
40,716 KB
testcase_10 AC 318 ms
40,844 KB
testcase_11 AC 344 ms
40,904 KB
testcase_12 AC 353 ms
40,960 KB
testcase_13 AC 336 ms
41,068 KB
testcase_14 AC 345 ms
40,892 KB
testcase_15 AC 327 ms
40,840 KB
testcase_16 AC 314 ms
40,948 KB
testcase_17 AC 316 ms
40,944 KB
testcase_18 AC 307 ms
41,020 KB
testcase_19 AC 307 ms
41,072 KB
testcase_20 AC 311 ms
40,832 KB
testcase_21 AC 313 ms
40,868 KB
testcase_22 AC 315 ms
40,832 KB
権限があれば一括ダウンロードができます

ソースコード

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