結果
問題 | No.2611 Count 01 |
ユーザー |
|
提出日時 | 2024-01-07 11:37:31 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 912 ms / 6,000 ms |
コード長 | 3,490 bytes |
コンパイル時間 | 3,904 ms |
コンパイル使用メモリ | 67,216 KB |
実行使用メモリ | 194,748 KB |
最終ジャッジ日時 | 2024-09-28 03:33:02 |
合計ジャッジ時間 | 22,668 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import strutils, sequtils, dequestype stdinReader = objectbuf: Deque[string]func newStdinReader(): stdinReader =result = stdinReader(buf: initDeque[string]())proc readString(sr: var stdinReader): string =if sr.buf.len == 0:sr.buf = stdin.readLine.split.toDequesr.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]st.data[i].addTo(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 2# st.data[k] = st.data[k * 2] + st.data[k * 2 + 1]st.data[k].addTo(st.data[k * 2], st.data[k * 2 + 1])func query[T, U, V](st: SegmentTree[T], l: int, r: int, ls, rs: U, v: V): V =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] = (result[i][j] + a[i][k] * b[k][j]) mod MODproc addTo(c: var Matrix, a, b: Matrix) =for i in 0 ..< a.len:for j in 0..i:c[i][j] = 0for k in j..i:c[i][j] = (c[i][j] + a[i][k] * b[k][j]) mod MODfunc `+`(a: Vec, b: Matrix): Vec =for i in 0 ..< a.len:for j in 0..i:result[j] = (result[j] + a[i] * b[i][j]) mod MODfunc `+`(a: Matrix, b: Vec): Vec =for i in 0 ..< a.len:for j in 0..i:result[i] = (result[i] + a[i][j] * b[j]) mod MODfunc `+`(a, b: Vec): int =for i in 0..<a.len:result = (result + a[i] * b[i]) 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], 0)echo ans