結果

問題 No.3239 Omnibus
コンテスト
ユーザー LyricalMaestro
提出日時 2026-09-21 03:06:08
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,511 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 64 ms
コンパイル使用メモリ 83,280 KB
実行使用メモリ 338,088 KB
最終ジャッジ日時 2026-09-21 03:06:28
合計ジャッジ時間 20,173 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 2 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3239

import math

def main():
    N, Q = map(int , input().split())
    S = input()
    S = [s for s in S]
    queries = []
    for _ in range(Q):
        values = input().split()
        queries.append(values)

    # 平方分割する
    sqrt_n = int(math.sqrt(N))
    block_num = N // sqrt_n + (1 if N % sqrt_n > 0 else 0)
    block_info = [{} for _ in range(block_num)]
    for block_index in range(block_num):
        start = block_index * sqrt_n
        end = min(N, (block_index + 1) * sqrt_n) - 1

        if sqrt_n >= 3:
            for i in range(start, end + 1 + 1- 3):
                word = "".join(S[i:(i + 3)])
                if word not in block_info[block_index]:
                    block_info[block_index][word] = [0, 0]
                block_info[block_index][word][0] += i + 1
                block_info[block_index][word][1] += 1

    for values in queries:
        if values[0] == "1":
            _, k, x = values
            k = int(k) - 1
            S[k] = x

            block_index = k // sqrt_n
            block_info[block_index].clear()
            start = block_index * sqrt_n
            end = min(N, (block_index + 1) * sqrt_n) - 1
            if sqrt_n >= 3:
                for i in range(start, end + 1 + 1 - 3):
                    word = "".join(S[i:(i + 3)])
                    if word not in block_info[block_index]:
                        block_info[block_index][word] = [0, 0]
                    block_info[block_index][word][0] += i + 1
                    block_info[block_index][word][1] += 1
        else:
            _, l, r, a = values
            l = int(l) -  1
            r = int(r) - 1

            block_index_l = l // sqrt_n
            block_index_r = r // sqrt_n
            if block_index_l == block_index_r:
                if r - l + 1 < 3:
                    print(0)
                else:
                    ans = 0
                    for i in range(l, r + 1 + 1 - 3):
                        word = "".join(S[i:(i + 3)])
                        if word == a:
                            ans += (i + 1 - l)
                    print(ans)
            else:
                ans = 0
                for i in range(l, (block_index_l + 1) * sqrt_n + 1 - 3):
                    word = "".join(S[i:(i + 3)])
                    if word == a:
                        ans += (i + 1 - l)

                for k_index in range(block_index_l + 1, block_index_r):
                    
                    array = block_info[k_index]
                    if a in array:
                        v0, v1 = array[a]
                        ans += v0 - l * v1

                end = min(N, (block_index_r + 1) * sqrt_n)
                for i in range(block_index_r * sqrt_n, end + 1 - 3):
                    word = "".join(S[i:(i + 3)])
                    if word == a:
                        ans += (i + 1 - l)

                # ブロックの境界部分についてもやる
                for k_index in range(block_index_l + 1, block_index_r + 1):
                    for d in range(-2, 0):
                        start = k_index * sqrt_n + d
                        end = k_index * sqrt_n + d + 2
                        if l <= start and end <= r:
                            word = "".join(S[start:(start + 3)])
                            if word == a:
                                ans += (start + 1 - l)
                print(ans)

                    











if __name__ == '__main__':
    main()
0