library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/aoj/0355.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0355"
#include <iostream>

#include "string/range_update_range_hash.hpp"
int main() {
    int n;
    std::string u;
    std::cin >> n >> u;
    auto rh = range_update_range_hash<>::from(u);
    int q;
    std::cin >> q;
    while (q--) {
        std::string t;
        std::cin >> t;
        if (t == "set") {
            int x, y;
            char z;
            std::cin >> x >> y >> z;
            rh.apply(--x, y, z);
        }
        if (t == "comp") {
            int a, b, c, d;
            std::cin >> a >> b >> c >> d;
            int sgn = rh.cmp(--a, b, --c, d);
            std::cout << (sgn == -1 ? 's' : sgn == 0 ? 'e' : 't') << '\n';
        }
    }
}
#line 1 "test/aoj/0355.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0355"
#include <iostream>

#line 2 "string/range_update_range_hash.hpp"
#include <algorithm>
#include <array>
#include <random>

#line 1 "atcoder/lazysegtree.hpp"



#line 5 "atcoder/lazysegtree.hpp"
#include <cassert>
#line 7 "atcoder/lazysegtree.hpp"
#include <vector>

#line 1 "atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder


#line 10 "atcoder/lazysegtree.hpp"

namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

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

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        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);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder


#line 2 "math/modint2305843009213693951.hpp"
#include <cstdint>
struct modint2305843009213693951 {
    using mint = modint2305843009213693951;

public:
    static constexpr uint64_t mod = 2305843009213693951;
    modint2305843009213693951() : _v(0) {
    }
    modint2305843009213693951(uint64_t v) : _v(fast_mod(v)) {
    }
    static constexpr uint64_t fast_mod(uint64_t v) {
        uint64_t u = v >> 61;
        uint64_t d = v & mod;
        uint64_t x = u + d;
        if (x > mod) x -= mod;
        return x;
    }
    uint64_t val() const {
        return _v;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= mod) _v -= mod;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= mod) _v += mod;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        static constexpr uint64_t mask31 = (uint64_t(1) << 31) - 1;
        static constexpr uint64_t mask30 = (uint64_t(1) << 30) - 1;
        uint64_t au = _v >> 31;
        uint64_t ad = _v & mask31;
        uint64_t bu = rhs._v >> 31;
        uint64_t bd = rhs._v & mask31;
        uint64_t m = ad * bu + au * bd;
        uint64_t mu = m >> 30;
        uint64_t md = m & mask30;
        _v = fast_mod((au * bu << 1) + mu + (md << 31) + ad * bd);
        return *this;
    }
    mint operator+() const {
        return *this;
    }
    mint operator-() const {
        return mint() - *this;
    }
    mint pow(uint64_t n) const {
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

private:
    uint64_t _v;
};
#line 2 "math/pow_sum_table.hpp"
template <typename mint>
struct pow_mod_sums {
    pow_mod_sums() {
    }
    pow_mod_sums(mint base, int n) : base(base) {
        ensure(n);
    }
    // sum(pow[0..i])
    const mint& operator[](int i) const {
        ensure(i);
        return pow_sums[i];
    }
    void ensure(int n) const {
        int sz = pow_sums.size();
        if (sz > n) return;
        pow_sums.resize(n + 1);
        pows.resize(n + 1);
        for (int i = sz; i <= n; i++) {
            pows[i] = base * pows[i - 1];
            pow_sums[i] = pow_sums[i - 1] + pows[i - 1];
        }
    }

private:
    mutable std::vector<mint> pow_sums{0};
    mutable std::vector<mint> pows{1};
    mint base;
    static constexpr int mod = mint::mod;
};
#line 3 "math/pow_table.hpp"
template <typename mint>
struct pow_mods {
    pow_mods() {
    }
    pow_mods(mint base, int n) : base(base) {
        ensure(n);
    }
    const mint& operator[](int i) const {
        ensure(i);
        return pows[i];
    }
    void ensure(int n) const {
        int sz = pows.size();
        if (sz > n) return;
        pows.resize(n + 1);
        for (int i = sz; i <= n; i++) pows[i] = base * pows[i - 1];
    }

private:
    mutable std::vector<mint> pows{1};
    mint base;
    static constexpr int mod = mint::mod;
};
#line 10 "string/range_update_range_hash.hpp"
template <int base_num = 1, typename mint = modint2305843009213693951>
struct range_update_range_hash {
public:
    range_update_range_hash() {
    }
    range_update_range_hash(const std::vector<int>& a) : n(a.size()) {
        std::vector<S> v(n);
        for (int i = 0; i < n; i++) {
            for (int base_id = 0; base_id < base_num; base_id++) {
                v[i].hash[base_id] = a[i];
            }
            v[i].size = 1;
            v[i].is_e = false;
        }
        segt = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>(v);
    }
    template <typename Iterable>
    static range_update_range_hash from(const Iterable& s) {
        std::vector<int> a;
        for (auto&& e : s) a.push_back(int(e));
        return range_update_range_hash(a);
    }

    template <typename T>
    void set(int p, T x) {
        segt.set(p, int(x));
    }
    std::array<mint, base_num> get(int p) {
        return segt.get(p).hash;
    }
    std::array<mint, base_num> prod(int l, int r) {
        return segt.prod(l, r).hash;
    }
    std::array<mint, base_num> all_prod() {
        return segt.all_prod();
    }
    template <typename T>
    void apply(int l, int r, T x) {
        segt.apply(l, r, {int(x), false});
    }
    int lcp(int l1, int r1, int l2, int r2) {
        int len = std::min(r1 - l1, r2 - l2);
        int ok = 0, ng = len + 1;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            bool f = prod(l1, l1 + mid) == prod(l2, l2 + mid);
            (f ? ok : ng) = mid;
        }
        return ok;
    }
    int cmp(int l1, int r1, int l2, int r2) {
        int x = std::min({lcp(l1, r1, l2, r2), r1 - l1, r2 - l2});
        if (l1 + x == r1 && l2 + x != r2) return -1;
        if (l1 + x == r1 && l2 + x == r2) return 0;
        if (l1 + x != r1 && l2 + x == r2) return 1;
        return get(l1 + x)[0].val() < get(l2 + x)[0].val() ? -1 : 1;
    }

private:
    static inline std::array<mint, base_num> gen_bases() {
        static std::mt19937_64 rng(std::random_device{}());
        std::array<mint, base_num> bases;
        for (int i = 0; i < base_num; i++) {
            while (true) {
                uint64_t k = std::uniform_int_distribution<uint64_t>(
                    1, mint::mod - 1)(rng);
                if (std::gcd(k, mint::mod - 1) != 1) continue;
                uint64_t b = mint(r).pow(k).val();
                if (b <= A) continue;
                bases[i] = b;
                break;
            }
        }
        return bases;
    }
    static inline std::array<pow_mod_sums<mint>, base_num> init_pow_sums(
        const std::array<mint, base_num>& bases) {
        std::array<pow_mod_sums<mint>, base_num> pow_sums;
        for (int i = 0; i < base_num; i++) {
            pow_sums[i] = pow_mod_sums<mint>(bases[i], 0);
        }
        return pow_sums;
    }
    static inline std::array<pow_mods<mint>, base_num> init_pows(
        const std::array<mint, base_num>& bases) {
        std::array<pow_mods<mint>, base_num> pows;
        for (int i = 0; i < base_num; i++) {
            pows[i] = pow_mods<mint>(bases[i], 0);
        }
        return pows;
    }
    static inline std::array<mint, base_num> bases = gen_bases();
    static inline std::array<pow_mod_sums<mint>, base_num> pow_sums =
        init_pow_sums(bases);
    static inline std::array<pow_mods<mint>, base_num> pows = init_pows(bases);
    int n;
    static constexpr uint64_t r = 37;
    static constexpr uint64_t A = 2147483647;

    struct S {
        std::array<mint, base_num> hash;
        int size;
        bool is_e;
    };
    static S op(S a, S b) {
        if (a.is_e) return b;
        if (b.is_e) return a;
        for (int base_id = 0; base_id < base_num; base_id++) {
            b.hash[base_id] += a.hash[base_id] * pows[base_id][b.size];
        }
        b.size += a.size;
        return b;
    }
    static S e() {
        return {std::array<mint, base_num>(), 0, true};
    }
    struct F {
        int f;
        bool is_id;
    };
    static S mapping(F f, S x) {
        if (!f.is_id) {
            for (int base_id = 0; base_id < base_num; base_id++) {
                x.hash[base_id] = f.f * pow_sums[base_id][x.size];
            }
        }
        return x;
    }
    static F composition(F f, F g) {
        return (f.is_id ? g : f);
    }
    static F id() {
        return {0, true};
    }
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> segt;
};
#line 5 "test/aoj/0355.test.cpp"
int main() {
    int n;
    std::string u;
    std::cin >> n >> u;
    auto rh = range_update_range_hash<>::from(u);
    int q;
    std::cin >> q;
    while (q--) {
        std::string t;
        std::cin >> t;
        if (t == "set") {
            int x, y;
            char z;
            std::cin >> x >> y >> z;
            rh.apply(--x, y, z);
        }
        if (t == "comp") {
            int a, b, c, d;
            std::cin >> a >> b >> c >> d;
            int sgn = rh.cmp(--a, b, --c, d);
            std::cout << (sgn == -1 ? 's' : sgn == 0 ? 'e' : 't') << '\n';
        }
    }
}
Back to top page