test/aoj/1418.test.cpp

View this file on GitHub
Last update: 2023-07-03 22:14:04+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1418

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1418"

#include <algorithm>
#include <array>
#include <iostream>
#include <set>

#include "../../math/prime_factorize_table.hpp"
#include "../../segment_tree/persistent_segment_tree.hpp"

#define _overload(_1, _2, _3, _4, name, ...) name
#define _rep1(Itr, N) _rep3(Itr, 0, N, 1)
#define _rep2(Itr, a, b) _rep3(Itr, a, b, 1)
#define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step)
#define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define rep(...) repeat(__VA_ARGS__)

#define ALL(X) begin(X), end(X)

using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

struct M {
    using T = array<i64, 3>;
    using value_type = T;
    const static i64 inf = 1ll << 60;
    static T identity() {
        return {inf, inf, inf};
    };
    static T operation(T lhs, T rhs) {
        T ret;
        int li = 0, ri = 0;
        rep(i, 3) {
            if (lhs[li] < rhs[ri]) {
                ret[i] = lhs[li];
                li++;
            } else {
                ret[i] = rhs[ri];
                ri++;
            }
        }
        return ret;
    };
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    i64 n, q;
    cin >> n >> q;
    vector<i64> a(n);
    for (auto &vs : a) cin >> vs;

    vector<PersistentSegmentTree<M>> seg;
    {
        PersistentSegmentTree<M> sg(n);
        rep(i, n) sg = sg.update(i, {0, M::inf, M::inf});
        seg.assign(1'000'000 + 1, sg);
    }

    PrimeFactorizeTable fact(1'000'000 + 1);

    rep(i, n) {
        if (a[i] > 1) {
            for (auto e : fact.factorize(a[i])) {
                auto [p, cnt] = e;
                seg[p] = seg[p].update(i, {cnt, M::inf, M::inf});
            }
        }
    }

    auto power = [&](i64 a, i64 b) {
        i64 ret = 1;
        while (b) {
            if (b & 1) {
                ret *= a;
            }
            a *= a;
            b >>= 1;
        }
        return ret;
    };
    auto enumerate = [&](i64 l, i64 k) {
        set<i64> st;
        rep(i, l, l + k + 1) {
            if (a[i] > 1) {
                for (auto e : fact.factorize(a[i])) {
                    st.insert(e.first);
                }
            }
        }
        return st;
    };
    rep(_, q) {
        char c;
        cin >> c;

        if (c == 'U') {
            i64 i, x;
            cin >> i >> x;
            --i;
            if (a[i] > 1) {
                for (auto e : fact.factorize(a[i])) {
                    auto [p, cnt] = e;
                    seg[p] = seg[p].update(i, {0, M::inf, M::inf});
                }
            }
            if (x > 1) {
                for (auto e : fact.factorize(x)) {
                    auto [p, cnt] = e;
                    seg[p] = seg[p].update(i, {cnt, M::inf, M::inf});
                }
            }
            a[i] = x;
        } else {
            i64 l, r, k;
            cin >> l >> r >> k;
            --l;
            i64 ans = 1;
            for (auto p : enumerate(l, k)) {
                i64 x = seg[p].fold(l, r)[k];
                if (x == M::inf) x = 0;
                ans *= power(p, x);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

#line 1 "test/aoj/1418.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1418"

#include <algorithm>
#include <array>
#include <iostream>
#include <set>

#line 1 "math/prime_factorize_table.hpp"



#include <cassert>
#include <utility>
#include <vector>

struct PrimeFactorizeTable {
    using P = std::pair<int, int>;  // prod(table[i], first ** second) = i
    std::vector<std::vector<P>> table;

    PrimeFactorizeTable(int n) : table(n + 1) {
        for (int i = 2; i <= n; i++) {
            if (!table[i].empty()) continue;
            for (int j = i; j <= n; j += i) {
                table[j].push_back(P(i, 0));
                int tmp = j;
                while (tmp > 1 && tmp % i == 0) {
                    table[j].back().second++;
                    tmp /= i;
                }
            }
        }
    };

    std::vector<P> factorize(int n) {
        assert(n > 1);
        return table[n];
    };
};


#line 1 "segment_tree/persistent_segment_tree.hpp"



#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#line 9 "segment_tree/persistent_segment_tree.hpp"

template <class Monoid>
struct PersistentSegmentTree {
    using uint = size_t;
    using T = typename Monoid::value_type;

    struct Node {
        T dat;
        Node *l = nullptr, *r = nullptr;

        Node(T dat) : dat(dat){};
    };

    Node *root;
    uint n;

    Node *merge_node(Node *lch, Node *rch) {
        T l = (lch ? lch->dat : Monoid::identity());
        T r = (rch ? rch->dat : Monoid::identity());
        Node *ret = new Node(Monoid::operation(l, r));
        ret->l = lch;
        ret->r = rch;

        return ret;
    };

    PersistentSegmentTree(const PersistentSegmentTree &) = default;

    PersistentSegmentTree &operator=(const PersistentSegmentTree &) = default;

    PersistentSegmentTree(uint n, Node *r) : root(r), n(n){};

    PersistentSegmentTree(uint n)
        : root(alloc(0, n, std::vector<T>(n, Monoid::identity()))), n(n){};

    template <class InputItr>
    PersistentSegmentTree(const InputItr first, const InputItr last)
        : n(std::distance(first, last)),
          root(alloc(0, n, std::vector<T>(first, last))){};

    Node *alloc(uint nl, uint nr, const std::vector<T> &v) {
        if (nr - nl <= 1)
            return new Node(v[nl]);
        else
            return merge_node(alloc(nl, (nl + nr) / 2, v),
                              alloc((nl + nr) / 2, nr, v));
    };

    const T fold(uint l, uint r) const {
        return fold(l, r, 0, n, root);
    };

    const T fold(uint ql, uint qr, uint nl, uint nr, const Node *np) const {
        if (np == nullptr || qr <= nl || nr <= ql)
            return Monoid::identity();

        else if (ql <= nl && nr <= qr)
            return np->dat;

        else
            return Monoid::operation(fold(ql, qr, nl, (nl + nr) / 2, np->l),
                                     fold(ql, qr, (nl + nr) / 2, nr, np->r));
    };

    PersistentSegmentTree update(uint idx, T d) {
        return set(idx, d);
    };

    PersistentSegmentTree set(uint idx, T d) {
        return PersistentSegmentTree(n, update(0, n, idx, d, root));
    };

    Node *update(uint nl, uint nr, uint idx, T d, Node *np) {
        if (idx < nl || nr <= idx)
            return np;
        else if (nr - nl == 1)
            return new Node(d);
        else
            return merge_node(update(nl, (nl + nr) / 2, idx, d, np->l),
                              update((nl + nr) / 2, nr, idx, d, np->r));
    };

    PersistentSegmentTree get_tree() {
        return *this;
    };

    T operator[](uint idx) {
        return fold(idx, idx + 1, 0, n, root);
    };
};


#line 10 "test/aoj/1418.test.cpp"

#define _overload(_1, _2, _3, _4, name, ...) name
#define _rep1(Itr, N) _rep3(Itr, 0, N, 1)
#define _rep2(Itr, a, b) _rep3(Itr, a, b, 1)
#define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step)
#define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define rep(...) repeat(__VA_ARGS__)

#define ALL(X) begin(X), end(X)

using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

struct M {
    using T = array<i64, 3>;
    using value_type = T;
    const static i64 inf = 1ll << 60;
    static T identity() {
        return {inf, inf, inf};
    };
    static T operation(T lhs, T rhs) {
        T ret;
        int li = 0, ri = 0;
        rep(i, 3) {
            if (lhs[li] < rhs[ri]) {
                ret[i] = lhs[li];
                li++;
            } else {
                ret[i] = rhs[ri];
                ri++;
            }
        }
        return ret;
    };
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    i64 n, q;
    cin >> n >> q;
    vector<i64> a(n);
    for (auto &vs : a) cin >> vs;

    vector<PersistentSegmentTree<M>> seg;
    {
        PersistentSegmentTree<M> sg(n);
        rep(i, n) sg = sg.update(i, {0, M::inf, M::inf});
        seg.assign(1'000'000 + 1, sg);
    }

    PrimeFactorizeTable fact(1'000'000 + 1);

    rep(i, n) {
        if (a[i] > 1) {
            for (auto e : fact.factorize(a[i])) {
                auto [p, cnt] = e;
                seg[p] = seg[p].update(i, {cnt, M::inf, M::inf});
            }
        }
    }

    auto power = [&](i64 a, i64 b) {
        i64 ret = 1;
        while (b) {
            if (b & 1) {
                ret *= a;
            }
            a *= a;
            b >>= 1;
        }
        return ret;
    };
    auto enumerate = [&](i64 l, i64 k) {
        set<i64> st;
        rep(i, l, l + k + 1) {
            if (a[i] > 1) {
                for (auto e : fact.factorize(a[i])) {
                    st.insert(e.first);
                }
            }
        }
        return st;
    };
    rep(_, q) {
        char c;
        cin >> c;

        if (c == 'U') {
            i64 i, x;
            cin >> i >> x;
            --i;
            if (a[i] > 1) {
                for (auto e : fact.factorize(a[i])) {
                    auto [p, cnt] = e;
                    seg[p] = seg[p].update(i, {0, M::inf, M::inf});
                }
            }
            if (x > 1) {
                for (auto e : fact.factorize(x)) {
                    auto [p, cnt] = e;
                    seg[p] = seg[p].update(i, {cnt, M::inf, M::inf});
                }
            }
            a[i] = x;
        } else {
            i64 l, r, k;
            cin >> l >> r >> k;
            --l;
            i64 ans = 1;
            for (auto p : enumerate(l, k)) {
                i64 x = seg[p].fold(l, r)[k];
                if (x == M::inf) x = 0;
                ans *= power(p, x);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}