#1198288 (C++23(gcc16)) No.2933 Range ROT Query

• 問題: No.2933 Range ROT Query
• ユーザー: urunea
• 提出日時: 2026-11-12 01:26:13
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2,219 ms / 3,000 ms
• コード長: 14,011 bytes
• コンパイル時間: 4,405 ms
• コンパイル使用メモリ: 265,932 KB
• 実行使用メモリ: 332,876 KB
• 最終ジャッジ日時: 2026-11-12 01:27:36
• 合計ジャッジ時間: 81,998 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 51

ソースコード

/*

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("Lesser")
                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("Lesser")
                else:
                    ans.append("Greater")

for i in ans:
    print(i)
*/

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

const long long MOD = (1ULL << 61) - 1;

// Modulo 2^61-1 の高速な足し算
inline long long add(long long a, long long b) {
    long long res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}

// Modulo 2^61-1 の高速な掛け算
inline long long mul(long long a, long long b) {
    __int128_t res = (__int128_t)a * b;
    res = (res >> 61) + (res & MOD);
    if (res >= MOD) res -= MOD;
    return (long long)res;
}

vector<long long> powb;

struct Node {
    long long k;
    long long length;
    long long l[26];
    
    Node() {
        k = 0;
        length = 0;
        for (int i = 0; i < 26; i++) l[i] = 0;
    }
};

// 比較クエリ用の軽量構造体（文字ごとの配列を持たない）
struct HashNode {
    long long k;
    long long length;
};

// 通常のマージ（更新用）
Node op(const Node& x, const Node& y) {
    if (x.length == 0) return y;
    if (y.length == 0) return x;
    
    Node res;
    long long py = powb[y.length]; // キャッシュして高速化
    res.k = add(mul(x.k, py), y.k);
    res.length = x.length + y.length;
    
    for (int i = 0; i < 26; i++) {
        res.l[i] = add(mul(x.l[i], py), y.l[i]);
    }
    return res;
}

// ハッシュ値のみのマージ（クエリ用・超高速）
inline HashNode op_hash(const HashNode& x, const HashNode& y) {
    if (x.length == 0) return y;
    if (y.length == 0) return x;
    return { add(mul(x.k, powb[y.length]), y.k), x.length + y.length };
}

Node mapping(long long f, const Node& S) {
    if (S.length == 0) return S;
    f %= 26;
    if (f < 0) f += 26;
    if (f == 0) return S;
    
    long long sum_p = 0;
    long long minus_p = 0;
    Node res;
    res.length = S.length;
    
    for (int i = 1; i <= 26; i++) {
        sum_p = add(sum_p, S.l[i - 1]);
        if (i + f >= 27) {
            minus_p = add(minus_p, S.l[i - 1]);
        }
        res.l[(i - 1 + f) % 26] = S.l[i - 1];
    }
    
    __int128_t val = S.k;
    val += (__int128_t)f * sum_p;
    val -= (__int128_t)26 * minus_p;
    
    long long rem = val % MOD;
    if (rem < 0) rem += MOD;
    res.k = rem;
    
    return res;
}

long long composition(long long f, long long g) {
    return (f + g) % 26;
}

struct LazySegTree {
    int _n, _log, _size;
    vector<Node> _d;
    vector<long long> _lz;

    LazySegTree(const vector<Node>& v) {
        _n = v.size();
        _log = 0;
        while ((1 << _log) < _n) _log++;
        _size = 1 << _log;
        
        _d.assign(2 * _size, Node());
        _lz.assign(_size, 0);
        
        for (int i = 0; i < _n; i++) {
            _d[_size + i] = v[i];
        }
        for (int i = _size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void update(int k) { _d[k] = op(_d[2 * k], _d[2 * k + 1]); }

    void all_apply(int k, long long f) {
        _d[k] = mapping(f, _d[k]);
        if (k < _size) _lz[k] = composition(f, _lz[k]);
    }

    void push(int k) {
        if (_lz[k] != 0) {
            all_apply(2 * k, _lz[k]);
            all_apply(2 * k + 1, _lz[k]);
            _lz[k] = 0;
        }
    }

    void apply(int l, int r, long long f) {
        if (l == r) return;
        l += _size; r += _size;
        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) all_apply(l++, f);
            if (r & 1) all_apply(--r, f);
            l >>= 1; r >>= 1;
        }
        l = l2; r = r2;
        for (int i = 1; i <= _log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    // ★追加：クエリ判定用の超軽量 prod 関数
    HashNode prod_hash(int l, int r) {
        if (l == r) return {0, 0};
        l += _size; r += _size;
        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        HashNode sml = {0, 0}, smr = {0, 0};
        while (l < r) {
            if (l & 1) {
                sml = op_hash(sml, {_d[l].k, _d[l].length});
                l++;
            }
            if (r & 1) {
                r--;
                smr = op_hash({_d[r].k, _d[r].length}, smr);
            }
            l >>= 1; r >>= 1;
        }
        return op_hash(sml, smr);
    }
};

int main() {
    // I/O高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    long long base = uniform_int_distribution<long long>(30, 1000000001)(rng);

    string S, T;
    if (!(cin >> S >> T)) return 0;

    int max_len = max(S.size(), T.size()) + 10;
    powb.assign(max_len, 0);
    powb[0] = 1;
    for (int i = 1; i < max_len; i++) {
        powb[i] = mul(powb[i - 1], base);
    }

    vector<Node> s_l(S.size());
    for (int i = 0; i < (int)S.size(); i++) {
        s_l[i].k = S[i] - 'a' + 1;
        s_l[i].length = 1;
        s_l[i].l[S[i] - 'a'] = 1;
    }

    vector<Node> t_l(T.size());
    for (int i = 0; i < (int)T.size(); i++) {
        t_l[i].k = T[i] - 'a' + 1;
        t_l[i].length = 1;
        t_l[i].l[T[i] - 'a'] = 1;
    }

    LazySegTree seg_S(s_l);
    LazySegTree seg_T(t_l);

    int Q;
    if (!(cin >> Q)) return 0;

    vector<string> ans;
    ans.reserve(Q);

    for (int i = 0; i < Q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            long long f;
            cin >> l >> r >> f;
            seg_S.apply(l - 1, r, f);
        } else if (type == 2) {
            int l, r;
            long long f;
            cin >> l >> r >> f;
            seg_T.apply(l - 1, r, f);
        } else if (type == 3) {
            int p;
            cin >> p;
            
            // ★二分探索の比較をすべて超軽量の prod_hash に変更！
            long long s = seg_S.prod_hash(p - 1, p).k;
            long long t = seg_T.prod_hash(p - 1, p).k;
            
            if (s > t) {
                ans.push_back("Greater");
            } else if (s < t) {
                ans.push_back("Lesser");
            } else {
                int left = p - 1;
                int right = min(S.size(), T.size());
                
                while (left + 1 < right) {
                    int mid = left + (right - left) / 2;
                    if (seg_S.prod_hash(p - 1, mid + 1).k == seg_T.prod_hash(p - 1, mid + 1).k) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                }
                
                if (right == (int)min(S.size(), T.size())) {
                    if (right == (int)S.size() && right == (int)T.size()) {
                        ans.push_back("Equals");
                    } else if (right == (int)S.size() && right != (int)T.size()) {
                        ans.push_back("Lesser");
                    } else {
                        ans.push_back("Greater");
                    }
                } else {
                    long long s_next = seg_S.prod_hash(right, right + 1).k;
                    long long t_next = seg_T.prod_hash(right, right + 1).k;
                    
                    if (s_next < t_next) {
                        ans.push_back("Lesser");
                    } else {
                        ans.push_back("Greater");
                    }
                }
            }
        }
    }

    for (const string& out : ans) cout << out << "\n";

    return 0;
}