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

• 問題: No.2933 Range ROT Query
• ユーザー: urunea
• 提出日時: 2026-11-12 01:53:43
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 7,374 bytes
• コンパイル時間: 4,591 ms
• コンパイル使用メモリ: 268,864 KB
• 実行使用メモリ: 389,304 KB
• 最終ジャッジ日時: 2026-11-12 01:56:11
• 合計ジャッジ時間: 133,454 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 36 TLE * 15

ソースコード

#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;
    vector<long long> l;
    
    Node() : k(0), length(0), l(26, 0) {}
    
    // mode=1 用の軽量なダミー配列を持つコンストラクタ
    Node(long long _k, long long _len, bool dummy) : k(_k), length(_len) {
        l.assign(1, 0); // Pythonの [0] に対応
    }
};

Node op(const Node& x, const Node& y, int mode) {
    if (x.length == 0) return y;
    if (y.length == 0) return x;
    
    long long xx_k = mul(x.k, powb[y.length]);
    long long new_k = add(xx_k, y.k);
    long long new_len = x.length + y.length;
    
    if (mode == 0) {
        Node res;
        res.k = new_k;
        res.length = new_len;
        for (int i = 0; i < 26; i++) {
            res.l[i] = add(mul(x.l[i], powb[y.length]), y.l[i]);
        }
        return res;
    } else {
        return Node(new_k, new_len, true);
    }
}

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], 0); }

    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);
        }
    }

    Node prod(int l, int r, int mode) {
        if (l == r) return Node();
        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);
        }
        Node sml, smr;
        while (l < r) {
            if (l & 1) sml = op(sml, _d[l++], mode);
            if (r & 1) smr = op(_d[--r], smr, mode);
            l >>= 1; r >>= 1;
        }
        return op(sml, smr, mode);
    }
};

int main() {
    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;
            
            long long s = seg_S.prod(p - 1, p, 1).k;
            long long t = seg_T.prod(p - 1, p, 1).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(p - 1, mid + 1, 1).k == seg_T.prod(p - 1, mid + 1, 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(right, right + 1, 1).k;
                    long long t_next = seg_T.prod(right, right + 1, 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;
}