結果
問題 | No.2611 Count 01 |
ユーザー |
|
提出日時 | 2024-01-07 15:35:32 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 1,062 ms / 6,000 ms |
コード長 | 3,281 bytes |
コンパイル時間 | 4,033 ms |
コンパイル使用メモリ | 67,092 KB |
実行使用メモリ | 229,504 KB |
最終ジャッジ日時 | 2024-09-28 03:34:43 |
合計ジャッジ時間 | 23,733 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import strutils, sequtils, deques# import nimproftype stdinReader = objectbuf: Deque[string]proc newStdinReader(): stdinReader =let buf = stdin.readAll.split.toDequeresult = stdinReader(buf: buf)proc readString(sr: var stdinReader): string =sr.buf.popFirstproc readInt(sr: var stdinReader): int =readString(sr).parseInttype SegmentTree[T] = objectn: intdata: seq[T]e: Tfunc init[T](n: int, e: T): SegmentTree[T] =var n2 = 1while n2 < n:n2 *= 2SegmentTree[T](n: n2, data: newSeqWith[T](n2 * 2, e), e: e)proc build[T](st: var SegmentTree[T], a: seq[T]) =for i, x in a:st.data[i + st.n] = xfor i in countdown(st.n - 1, 1):st.data[i] = st.data[i * 2] + st.data[i * 2 + 1]proc update[T](st: var SegmentTree[T], i: int, x: T) =var k = i + st.nst.data[k] = xwhile k > 1:k = k div 2st.data[k] = st.data[k * 2] + st.data[k * 2 + 1]func query[T, U](st: SegmentTree[T], l: int, r: int, ls, rs: U): auto =varl = l + st.nr = r + st.nvarls = lsrs = rswhile l < r:if (l and 1) == 1:ls = ls + st.data[l]l += 1if (r and 1) == 1:r -= 1rs = st.data[r] + rsl = l div 2r = r div 2ls + rsconst MOD = 998244353type Vec = array[6, int]type Matrix = array[6, array[6, int]]func `+`(a, b: Matrix): Matrix =for i in 0 ..< a.len:for j in 0..i:for k in j..i:result[i][j] += a[i][k] * b[k][j]for i in 0 ..< a.len:for j in 0..i:result[i][j] = result[i][j] mod MODfunc `+`(a: Vec, b: Matrix): Vec =for i in 0 ..< a.len:for j in 0..i:result[j] += a[i] * b[i][j]for i in 0 ..< a.len:result[i] = result[i] mod MODfunc `+`(a: Matrix, b: Vec): Vec =for i in 0 ..< a.len:for j in 0..i:result[i] += a[i][j] * b[j]for i in 0 ..< a.len:result[i] = result[i] mod MODfunc `+`(a, b: Vec): int =for i in 0..<a.len:result += a[i] * b[i]result = result mod MODlet node: array[2, Matrix] = [[[1, 0, 0, 0, 0, 0],[1, 1, 0, 0, 0, 0],[1, 1, 1, 0, 0, 0],[0, 0, 0, 1, 0, 0],[0, 0, 0, 1, 1, 0],[0, 0, 0, 1, 1, 1],],[[1, 0, 0, 0, 0, 0],[1, 1, 0, 0, 0, 0],[0, 0, 1, 0, 0, 0],[1, 1, 0, 1, 0, 0],[0, 0, 1, 0, 1, 0],[0, 0, 1, 0, 1, 1],]]let identity: Matrix = [[1, 0, 0, 0, 0, 0],[0, 1, 0, 0, 0, 0],[0, 0, 1, 0, 0, 0],[0, 0, 0, 1, 0, 0],[0, 0, 0, 0, 1, 0],[0, 0, 0, 0, 0, 1],]var reader = newStdinReader()let (n, q) = (reader.readInt, reader.readInt)let s = reader.readStringvar sSeq = s.mapIt(int(it) - int('0'))var st = init[Matrix](n, identity)st.build(sSeq.mapIt(node[it]))for _ in 0..<q:let t = reader.readIntif t == 1:let i = reader.readInt - 1sSeq[i] = 1 - sSeq[i]st.update(i, node[sSeq[i]])else:let (l, r) = (reader.readInt - 1, reader.readInt)let ans = st.query(l, r, [0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0])echo ans