結果
問題 |
No.3239 Omnibus
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:49:22 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 518 ms / 10,000 ms |
コード長 | 2,516 bytes |
コンパイル時間 | 12,812 ms |
コンパイル使用メモリ | 315,668 KB |
実行使用メモリ | 62,196 KB |
最終ジャッジ日時 | 2025-08-15 22:49:54 |
合計ジャッジ時間 | 24,862 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
TH = 800 n, q = read_line.split.map(&.to_i) s = read_line.chars pos = Hash(Int32, Set(Int32)).new { |h, k| h[k] = Set(Int32).new } (n - 2).times do |i| pos[encode(s[i], s[i + 1], s[i + 2])] << i end bit_sums = Hash(Int32, BIT(Int64)).new bit_cnts = Hash(Int32, BIT(Int64)).new pos.each do |k, s| if s.size >= TH bit_sum = BIT(Int64).new(n) bit_cnt = BIT(Int64).new(n) s.each do |i| bit_sum.add(i + 1, i) bit_cnt.add(i + 1, 1) end bit_sums[k] = bit_sum bit_cnts[k] = bit_cnt end end q.times do qs = read_line.split if qs[0] == "1" k = qs[1].to_i - 1 x = qs[2][0] {0, k - 2}.max.upto({n - 3, k}.min) do |i| v = encode(s[i], s[i + 1], s[i + 2]) pos[v].delete(i) if bit_sums.has_key?(v) bit_sums[v].add(i + 1, -i) bit_cnts[v].add(i + 1, -1) end end s[k] = x {0, k - 2}.max.upto({n - 3, k}.min) do |i| v = encode(s[i], s[i + 1], s[i + 2]) pos[v] << i if pos[v].size == TH && !bit_sums.has_key?(v) bit_sum = BIT(Int64).new(n) bit_cnt = BIT(Int64).new(n) pos[v].each do |i| bit_sum.add(i + 1, i) bit_cnt.add(i + 1, 1) end bit_sums[v] = bit_sum bit_cnts[v] = bit_cnt elsif bit_sums.has_key?(v) bit_sums[v].add(i + 1, i) bit_cnts[v].add(i + 1, 1) end end else l = qs[1].to_i - 1 r = qs[2].to_i - 1 a = encode(qs[3][0], qs[3][1], qs[3][2]) if r - l < 2 puts 0 next end if pos[a].size < TH ans = 0i64 pos[a].each do |i| if l <= i <= r - 2 ans += i - l + 1 end end puts ans else sum = bit_sums[a].sum(l + 1, r - 1) cnt = bit_cnts[a].sum(l + 1, r - 1) puts sum - cnt.to_i64 * (l - 1) end end end def encode(c0, c1, c2) (c0 - 'a') * 26 * 26 + (c1 - 'a') * 26 + (c2 - 'a') end class BIT(T) # 1-indexed def initialize(size : Int) len = 1 while len < size len *= 2 end @v = Array(T).new(len + 1, T.zero) end def cumulative_sum(index : Int) ret = T.zero while index > 0 ret += @v[index] index &= index - 1 end ret end def sum(l : Int, r : Int) cumulative_sum(r) - cumulative_sum(l - 1) end def add(index : Int, val : T) while index < @v.size @v[index] += val index += (index & -index) end end def set(index : Int, val : T) old = sum(index, index) add(index, val - old) end end