test/aoj/1418_2.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/dynamic_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;
using u8 = unsigned char;

struct M {
    using T = array<int, 4>;
    using value_type = T;
    const static u8 inf = 100;
    static T identity() {
        return {inf, inf, inf, 0};
    };
    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++;
            }
        }
        ret[3] = lhs[3] + rhs[3];
        return ret;
    };
};

struct SUM {
    using T = int;
    using value_type = T;
    static T identity() {
        return 0;
    };
    static T operation(T lhs, T rhs) {
        return lhs + rhs;
    };
};

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

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

    vector<DynamicSegmentTree<M>> seg(1'000'000 + 1);

    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].update(i, {u8(cnt), M::inf, M::inf, 1});
            }
        }
    }

    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<int> 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].update(i, M::identity());
                }
            }
            if (x > 1) {
                for (auto e : fact.factorize(x)) {
                    auto [p, cnt] = e;
                    seg[p].update(i, {u8(cnt), M::inf, M::inf, 1});
                }
            }
            a[i] = x;
        } else {
            i64 l, r, k;
            cin >> l >> r >> k;
            --l;
            i64 ans = 1;
            for (auto p : enumerate(l, k)) {
                i64 z = (r - l) - seg[p].fold(l, r)[3];
                i64 x;
                if (z > k)
                    x = 0;
                else
                    x = seg[p].fold(l, r)[k - z];

                if (x == M::inf) x = 0;
                ans *= power(p, x);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

#line 1 "test/aoj/1418_2.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/dynamic_segment_tree.hpp"



template <class Monoid>
struct DynamicSegmentTree {
    using T = typename Monoid::value_type;
    using llong = long long;

    struct Node {
        T v;
        Node *left, *right;
        Node(T v) : v(v), left(nullptr), right(nullptr){};
    };

    Node *root = nullptr;
    llong L = 0, R = 0;

    DynamicSegmentTree() = default;

    inline void eval(Node &u) {
        T lv = Monoid::identity(), rv = Monoid::identity();
        if (u.left) lv = u.left->v;
        if (u.right) rv = u.right->v;
        u.v = Monoid::operation(lv, rv);
    };

    inline void expand(llong i) {
        if (L == R) {
            R++;
            while (i >= R) R += R - L;
            while (i < L) L -= R - L;
            root = new Node(Monoid::identity());
        } else {
            Node *tmp;

            while (i >= R) {
                R += R - L;
                tmp = new Node(root->v);
                tmp->left = root;
                root = tmp;
            }

            while (i < L) {
                L -= R - L;
                tmp = new Node(root->v);
                tmp->right = root;
                root = tmp;
            }
        }
    };

    inline void update(llong i, T v) {
        if (i < L || R <= i) expand(i);
        update(root, L, R, i, v);
    };

    void update(Node *node, llong nl, llong nr, llong k, T v) {
        if (nr - nl <= 1) {
            node->v = v;
            return;
        }

        llong mid = (nl + nr) / 2;
        if (k < mid) {
            if (!node->left) node->left = new Node(Monoid::identity());

            update(node->left, nl, (nl + nr) / 2, k, v);
        } else {
            if (!node->right) node->right = new Node(Monoid::identity());

            update(node->right, (nl + nr) / 2, nr, k, v);
        }

        eval(*node);
        return;
    }

    // [l, r)
    inline T fold(llong l, llong r) {
        if (l < L) expand(l);
        if (r > R) expand(r);
        return fold(root, L, R, l, r);
    };

    T fold(Node *node, llong nl, llong nr, llong ql, llong qr) {
        if (ql <= nl && nr <= qr) return node->v;

        T lv = Monoid::identity(), rv = Monoid::identity();
        llong mid = (nl + nr) / 2;

        if (node->left && ql < mid && nl < qr)
            lv = fold(node->left, nl, mid, ql, qr);

        if (node->right && ql < nr && mid < qr)
            rv = fold(node->right, mid, nr, ql, qr);

        return Monoid::operation(lv, rv);
    };

    T operator[](const llong k) {
        return fold(k, k + 1);
    };
};


#line 10 "test/aoj/1418_2.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;
using u8 = unsigned char;

struct M {
    using T = array<int, 4>;
    using value_type = T;
    const static u8 inf = 100;
    static T identity() {
        return {inf, inf, inf, 0};
    };
    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++;
            }
        }
        ret[3] = lhs[3] + rhs[3];
        return ret;
    };
};

struct SUM {
    using T = int;
    using value_type = T;
    static T identity() {
        return 0;
    };
    static T operation(T lhs, T rhs) {
        return lhs + rhs;
    };
};

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

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

    vector<DynamicSegmentTree<M>> seg(1'000'000 + 1);

    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].update(i, {u8(cnt), M::inf, M::inf, 1});
            }
        }
    }

    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<int> 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].update(i, M::identity());
                }
            }
            if (x > 1) {
                for (auto e : fact.factorize(x)) {
                    auto [p, cnt] = e;
                    seg[p].update(i, {u8(cnt), M::inf, M::inf, 1});
                }
            }
            a[i] = x;
        } else {
            i64 l, r, k;
            cin >> l >> r >> k;
            --l;
            i64 ans = 1;
            for (auto p : enumerate(l, k)) {
                i64 z = (r - l) - seg[p].fold(l, r)[3];
                i64 x;
                if (z > k)
                    x = 0;
                else
                    x = seg[p].fold(l, r)[k - z];

                if (x == M::inf) x = 0;
                ans *= power(p, x);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}