This documentation is automatically generated by online-judge-tools/verification-helper
#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;
}