< uruneaさんのAI生成コード置き場

ロリハ

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

import random

S = input().strip()
N = len(S)
base = random.randint(256, 10**6)
mods = [1000000007, 1000000009]
M = len(mods)

A = [ord(c) - 96 for c in S]

H = [[0]*(N+1) for _ in range(M)]  
P = [[1]*(N+1) for _ in range(M)] 

for j in range(M):
    mod = mods[j]
    for i in range(N):
        H[j][i+1] = (H[j][i]*base + A[i]) % mod
        P[j][i+1] = (P[j][i]*base) % mod

#半開区間[l, r)
def get_hash(l, r):
    res = []
    for j in range(M):
        mod = mods[j]
        val = (H[j][r] - H[j][l]*P[j][r-l]) % mod
        res.append(val)
    return (res[0] << 32) ^ res[1]

#---------------------------------------------------------

import random

# 2つの異なる大きな素数を用意
mod1 = 998244353
mod2 = 1000000007

# 実行ごとに完全に独立したランダム基数を生成（ハック絶対回避）
base1 = random.randint(2, mod1 - 2)
base2 = random.randint(2, mod2 - 2)

# 状態 S: (h1, h2, B1, B2, s1, s2)
# h: 区間のハッシュ値
# B: base^length (左区間をシフトさせる係数)
# s: base^0 + ... + base^(length-1) (一括上書き時の計算用)
def op(x, y):
    xh1, xh2, xB1, xB2, xs1, xs2 = x
    yh1, yh2, yB1, yB2, ys1, ys2 = y
    
    # 2つのモジュロで全く同じ計算を並行して行う
    h1 = (xh1 * yB1 + yh1) % mod1
    B1 = (xB1 * yB1) % mod1
    s1 = (xs1 * yB1 + ys1) % mod1
    
    h2 = (xh2 * yB2 + yh2) % mod2
    B2 = (xB2 * yB2) % mod2
    s2 = (xs2 * yB2 + ys2) % mod2
    
    return (h1, h2, B1, B2, s1, s2)

def e():
    # 長さ0の単位元
    return (0, 0, 1, 1, 0, 0)

def mapping(f, S):
    if f == -1: # 操作の単位元
        return S
    _h1, _h2, B1, B2, s1, s2 = S
    
    # 区間全体を文字 f に上書き
    h1 = (f * s1) % mod1
    h2 = (f * s2) % mod2
    
    return (h1, h2, B1, B2, s1, s2)

def composition(f, g):
    return f if f != -1 else g

def id_v():
    return -1


# ==========================================
# 初期化と判定の確実な使い方
# ==========================================
"""
S_str = "abacaba"

# 各文字 c について、初期状態 (h1, h2, base1^1, base2^1, sum_b1, sum_b2) を作る
# 初期長さは1なので、B=base, sum=1 となる
aa = [(ord(c), ord(c), base1, base2, 1, 1) for c in S_str]

seg = LazySegTree(op, e(), mapping, composition, id_v(), aa)

# ハッシュの比較時は、モジュロ1とモジュロ2の両方の値が一致するか確認する
h_left = seg.prod(0, 3)   # 戻り値は6要素のタプル
h_right = seg.prod(4, 7)

# h[0]がmod1のハッシュ、h[1]がmod2のハッシュ
if h_left[0] == h_right[0] and h_left[1] == h_right[1]:
    print("Match!")
"""
# ==========================================
# クエリ1：区間変更（Range Update）
# ==========================================
# 例: 区間 [1, 4) の文字をすべて "z" に一括で上書き変更する
update_char = ord("z")
seg.apply(1, 4, update_char)


# ==========================================
# クエリ2：一点変更（Point Update）
# ==========================================
# 例: インデックス 2 の文字だけを "x" に変更する
p = 2
new_char = ord("x")

# 方法1: apply を使って「長さ1の区間」として処理する（最も簡潔）
seg.apply(p, p + 1, new_char)

# 方法2: set を使ってノードの状態データを直接上書きする
# ※set の場合は mapping を経由しないため、初期化時と同じ「長さ1の6要素タプル」を直接渡す必要があります
seg.set(p, (new_char, new_char, base1, base2, 1, 1))