#1189907 (PyPy3) No.3239 Omnibus

• 問題: No.3239 Omnibus
• ユーザー: LyricalMaestro
• 提出日時: 2026-09-21 03:51:19
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,170 bytes
• コンパイル時間: 66 ms
• コンパイル使用メモリ: 82,092 KB
• 実行使用メモリ: 337,012 KB
• 最終ジャッジ日時: 2026-09-21 03:55:09
• 合計ジャッジ時間: 96,963 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 18 TLE * 12 -- * 3

ソースコード

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

import math

def same_word(S, l, a):
    for j in range(len(a)):
        if S[l + j] != a[j]:
            return False
    return True

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_score = [{} for _ in range(block_num)]
    block_info_count = [{} 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)

        if sqrt_n >= 3:
            target_block_info_score = block_info_score[block_index]
            target_block_info_count = block_info_count[block_index]
            for i in range(start, end):
                end0 = i + 2
                if end0 < end:
                    word = "".join(S[i:(i + 3)])
                    if word not in target_block_info_score:
                        target_block_info_score[word] = 0
                    target_block_info_score[word] += i + 1
                    if word not in target_block_info_count:
                        target_block_info_count[word] = 0
                    target_block_info_count[word] += 1

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

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

            if sqrt_n >= 3:
                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):
                            start = i
                            end = i + 2
                            if l <= start and end <= r:
                                if same_word(S, i, a):
                                    ans += (i + 1 - l)
                        print(ans)
                else:
                    ans = 0
                    for i in range(l, (block_index_l + 1) * sqrt_n):
                        start = i
                        end = i + 2
                        if l <= start and end < (block_index_l + 1) * sqrt_n:
                            if same_word(S, i, a):
                                ans += (i + 1 - l)

                    for k_index in range(block_index_l + 1, block_index_r):
                        array0 = block_info_score[k_index]
                        array1 = block_info_count[k_index]
                        if a in array0:
                            ans += array0[a] - l * array1[a]

                    end0 = min(r + 1, (block_index_r + 1) * sqrt_n)
                    for i in range(block_index_r * sqrt_n, end0):
                        start = i
                        end = i + 2
                        if block_index_r * sqrt_n <= start and end < end0:
                            if same_word(S, i, a):
                                ans += (i + 1 - l)

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

                    











if __name__ == '__main__':
    main()