結果

問題 No.2933 Range ROT Query
ユーザー urunea
提出日時 2026-11-12 00:53:45
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 6,164 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 490 ms
コンパイル使用メモリ 65,024 KB
実行使用メモリ 718,684 KB
最終ジャッジ日時 2026-11-12 00:54:03
合計ジャッジ時間 10,755 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 7 WA * 3 MLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import random

class LazySegTree:
    def __init__(self, op, e, mapping, composition, id_v, v):
        n = len(v)
        log = 0
        while (1 << log) < n:
            log += 1
        size = 1 << log
        
        d = [e] * (2 * size)
        lz = [id_v] * size
        
        for i in range(n):
            d[size + i] = v[i]

        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_v
        
        self._n = n
        self._log = log
        self._size = size
        self._d = d
        self._lz = lz
        
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k):
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k, f):
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])

    def _push(self, k):
        if self._lz[k] != self._id:
            self._all_apply(2 * k, self._lz[k])
            self._all_apply(2 * k + 1, self._lz[k])
            self._lz[k] = self._id
    
    def set(self, p, x):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, l, r):
        if l == r:
            return self._e
        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l: self._push(l >> i)
            if ((r >> i) << i) != r: self._push((r - 1) >> i)
        
        sml, smr = self._e, self._e
        while l < r:
            if l & 1:
                sml = self._op(sml, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self._op(self._d[r], smr)
            l >>= 1
            r >>= 1
        return self._op(sml, smr)

    def all_prod(self):
        return self._d[1]

    def apply(self, l, r, f):
        if l == r:
            return
        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l: self._push(l >> i)
            if ((r >> i) << i) != r: self._push((r - 1) >> i)
        
        l2, r2 = l, r
        while l < r:
            if l & 1:
                self._all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._all_apply(r, f)
            l >>= 1
            r >>= 1
        
        l, r = l2, r2
        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l: self._update(l >> i)
            if ((r >> i) << i) != r: self._update((r - 1) >> i)

    def apply_point(self, p, f):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = self._mapping(f, self._d[p])
        for i in range(1, self._log + 1):
            self._update(p >> i)


#右区間と左区間をマージ
def op(x, y):
    x_k, x_len, x_l = x
    y_k, y_len, y_l = y
    xx_k = (x_k*powb[y_len])%mod
    new_k = (xx_k+y_k)%mod
    new_len = x_len+y_len
    new_l = [0]*26
    for i in range(26):
        new_l[i] = ((x_l[i]*powb[y_len])%mod+y_l[i])%mod
    return (new_k, new_len, new_l)

#値の単位元
#op(x, e) = op(e, x) = x を満たす必要がある。
def e():
    return (0, 0, 0)

#区間に区間変更値fを付与
def mapping(f, S):
    S_k, S_len, S_l = S
    sum_p, minus_p = 0, 0
    new_sl = [0]*26
    for i in range(1, 27):
        sum_p += S_l[i-1]
        if i+f >= 27:
            minus_p += S_l[i-1]
        new_sl[(i-1+f)%26] = S_l[i-1]
    new_k = (S_k+f*sum_p-26*minus_p)%mod
    return (new_k, S_len, new_sl)

#元々溜まっていたgに新たに降ってきたfを合わせる
def composition(f, g):
    return (f + g)%26

#何も操作しないときの状態(操作の単位元)
#mapping(id, x) = x と composition(f, id) = f を満たす必要がある。
#例えば区間乗算なら、1を掛けても何も変わらないのでid=1
#区間代入なら、入力で与えられない極端な数字6*10**18など
def id():
    return 0


base = random.randint(30, 10**9+1)
mod = 2**61-1

S = list(map(str, input()))
T = list(map(str, input()))
powb = [pow(base, i, mod) for i in range(max(len(S), len(T))+10)]
s_l = []
for s in S:
    p = [0]*26
    p[(ord(s) - ord('a'))] = 1
    s_l.append([(ord(s) - ord('a') + 1), 1, p])
t_l = []
for t in T:
    p = [0]*26
    p[(ord(t) - ord('a'))] = 1
    t_l.append([(ord(t) - ord('a') + 1), 1, p])

seg_S = LazySegTree(op, (0, 0, [0]*26), mapping, composition, 0, s_l)
seg_T = LazySegTree(op, (0, 0, [0]*26), mapping, composition, 0, t_l)
Q = int(input())
ans = []
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        seg_S.apply(q[1]-1, q[2], q[3])
    elif q[0] == 2:
        seg_T.apply(q[1]-1, q[2], q[3])
    else:
        p = q[1]
        s, t = seg_S.prod(p-1, p)[0], seg_T.prod(p-1, p)[0]
        if s > t:
            ans.append("Greater")
        elif s < t:
            ans.append("Lesser")
        else:
            left, right = p-1, min(len(S), len(T))
            while left + 1 < right:
                mid = (left+right)//2
                if seg_S.prod(p-1, mid+1)[0] == seg_T.prod(p-1, mid+1)[0]:
                    left = mid
                else:
                    right = mid
            if right == min(len(S), len(T)):
                if right == len(S) and right == len(T):
                    ans.append("Equals")
                elif right == len(S) and right != len(T):
                    ans.append("Lessor")
                else:
                    ans.append("Greater")
            else:
                s, t = seg_S.prod(right, right+1)[0], seg_T.prod(right, right+1)[0]
                if s < t:
                    ans.append("Lessor")
                else:
                    ans.append("Greater")

for i in ans:
    print(i)
0