結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 rogi52
|
| 提出日時 | 2026-04-18 00:55:27 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 376 ms / 2,000 ms |
| コード長 | 32,632 bytes |
| 記録 | |
| コンパイル時間 | 2,783 ms |
| コンパイル使用メモリ | 266,824 KB |
| 実行使用メモリ | 12,604 KB |
| 最終ジャッジ日時 | 2026-04-18 00:55:46 |
| 合計ジャッジ時間 | 14,187 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 |
ソースコード
#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <iostream>
#include <queue>
#include <cassert>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <random>
#include <bit>
#include <array>
#include <cctype>
#include <set>
#include <map>
using namespace std;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;
#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;
#define FOR1(n) for(int _ = 0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n) for(int i = 0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t) for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define REV1(n) for(int _ = (n) - 1; _ >= 0 ; _--)
#define REV2(i, n) for(int i = (n) - 1; i >= 0 ; i--)
#define REV3(i, s, t) for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)
#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))
#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]
template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;
template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; }
template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; }
i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) < 0 && n % d != 0); }
i64 ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }
template < class T, class F > T bin_search(T ok, T ng, const F& check) { while((ok > ng ? ok - ng : ng - ok) > 1) { T mid = midpoint(ok, ng); (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, const F& check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(const vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(const vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }
istream& operator >> (istream& is, i128& x) {
string s; is >> s;
int m = (s[0] == '-');
x = 0;
FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
if(m) x *= -1;
return is;
}
ostream& operator << (ostream& os, const i128& x) {
if(x == 0) return os << '0';
i128 y = x; if(y < 0) { os << '-'; y *= -1; }
vector<int> ny;
while(y) ny.push_back(y % 10), y /= 10;
REV(i, ssize(ny)) os << ny[i];
return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }
template < class T > ostream& operator << (ostream& os, const vector< T >& a) {
const int n = a.size();
FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
return os;
}
template < class T > int print_n(const vector< T >& a) { for(const T& x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
void prec(int n) { cout << fixed << setprecision(n); }
void flush() { cout.flush(); }
}
vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int> operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int> operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }
template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }
int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }
int Yes() { return print("Yes"); }
int No() { return print("No"); }
constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
template < class T > constexpr T infty = 0;
template <> constexpr int infty<int> = 1e9;
template <> constexpr int infty<u32> = 1e9;
template <> constexpr i64 infty<i64> = 1e18;
template <> constexpr u64 infty<u64> = 1e18;
namespace bit {
int pop(int x) { return popcount<u32>(x); }
int pop(u32 x) { return popcount<u32>(x); }
int pop(i64 x) { return popcount<u64>(x); }
int pop(u64 x) { return popcount<u64>(x); }
int parity(int x) { return __builtin_parity(x); }
int parity(u32 x) { return __builtin_parity(x); }
int parity(i64 x) { return __builtin_parityll(x); }
int parity(u64 x) { return __builtin_parityll(x); }
int sgn(int x) { return parity(x) ? -1 : +1; }
int sgn(u32 x) { return parity(x) ? -1 : +1; }
int sgn(i64 x) { return parity(x) ? -1 : +1; }
int sgn(u64 x) { return parity(x) ? -1 : +1; }
int top(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(u32 x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(i64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int top(u64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int low(int x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(u32 x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(i64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int low(u64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int ceil(int x) { return bit_ceil<u32>(x); }
i64 ceil(i64 x) { return bit_ceil<u64>(x); }
int floor(int x) { return bit_floor<u32>(x); }
i64 floor(i64 x) { return bit_floor<u64>(x); }
}
// (-1)^n
int parity_sign(int n) { return n % 2 == 0 ? +1 : -1; }
template < class Key, class Value >
struct key_value {
Key key;
Value value;
};
template < class Value > key_value<int, Value> min(const vector<Value>& a) {
assert(1 <= ssize(a));
auto itr = min_element(a.begin(), a.end());
return {static_cast<int>(distance(a.begin(), itr)), *itr};
}
template < class Value > key_value<int, Value> max(const vector<Value>& a) {
assert(1 <= ssize(a));
auto itr = max_element(a.begin(), a.end());
return {static_cast<int>(distance(a.begin(), itr)), *itr};
}
#line 1 "/Users/korogi/Desktop/cp-cpp/util/grid.hpp"
struct grid {
int H, W;
grid(int H, int W) : H(H), W(W) {}
static constexpr pair<int, int> dir4[] = {
{-1, 0},
{ 0, -1}, { 0, +1},
{+1, 0}
};
static constexpr pair<int, int> dir8[] = {
{-1, -1}, {-1, 0}, {-1, +1},
{ 0, -1}, { 0, +1},
{+1, -1}, {+1, 0}, {+1, +1}
};
bool contains(int i, int j) const {
return 0 <= i and i < H and 0 <= j and j < W;
}
template < class F >
void for_each_dir4(int i, int j, const F& f) const {
for(const auto [di, dj] : dir4) {
const int ni = i + di, nj = j + dj;
if(contains(ni, nj)) f(ni, nj);
}
}
template < class F >
void for_each_dir8(int i, int j, const F& f) const {
for(const auto [di, dj] : dir8) {
const int ni = i + di, nj = j + dj;
if(contains(ni, nj)) f(ni, nj);
}
}
};
#line 1 "/Users/korogi/Desktop/cp-cpp/util/imos.hpp"
template < class Sum > struct psum1D {
int n;
vector<Sum> s;
psum1D() : n(0), s(1, Sum()) {}
template < class Value >
psum1D(const vector<Value>& a) : n(ssize(a)), s(n + 1, Sum()) {
FOR(i, n) s[i + 1] = s[i] + static_cast<Sum>(a[i]);
}
// [l, r)
Sum v(int l, int r) const {
assert(0 <= l and l <= r and r <= n);
return s[r] - s[l];
}
void push_back(const Sum& x) {
s.push_back(s.back() + x);
n += 1;
}
};
template < class Value > struct psum2D {
int H, W;
vector<vector<Value>> A;
bool built;
psum2D(int H, int W) : H(H), W(W), A(H + 1, vector(W + 1, Value(0))), built(false) {}
// A[x][y] += v
void add(int x, int y, Value v) {
assert(not built);
assert(0 <= x and x < H);
assert(0 <= y and y < W);
A[x + 1][y + 1] += v;
}
void build() {
FOR(x, H) FOR(y, W + 1) A[x + 1][y] += A[x][y];
FOR(x, H + 1) FOR(y, W) A[x][y + 1] += A[x][y];
built = true;
}
// [xL, xR) * [yL, yR)
Value sum(int xL, int xR, int yL, int yR) {
assert(built);
assert(0 <= xL and xL <= xR and xR <= H);
assert(0 <= yL and yL <= yR and yR <= W);
return A[xR][yR] - A[xR][yL] - A[xL][yR] + A[xL][yL];
}
Value get(int x, int y) {
assert(built);
assert(0 <= x and x < H);
assert(0 <= y and y < W);
return sum(x, x + 1, y, y + 1);
}
};
template < class Value > struct imos2D {
int H, W;
vector<vector<Value>> A;
bool built;
imos2D(int H, int W) : H(H), W(W), A(H + 1, vector(W + 1, Value(0))), built(false) {}
void add(int xL, int xR, int yL, int yR, Value v) {
assert(not built);
assert(0 <= xL and xL <= xR and xR <= H);
assert(0 <= yL and yL <= yR and yR <= W);
A[xL][yL] += v;
A[xR][yL] -= v;
A[xL][yR] -= v;
A[xR][yR] += v;
}
void build() {
assert(not built);
FOR(i, H + 1) FOR(j, W) A[i][j + 1] += A[i][j];
FOR(i, H) FOR(j, W + 1) A[i + 1][j] += A[i][j];
built = true;
}
Value get(int x, int y) {
assert(built);
assert(0 <= x and x < H);
assert(0 <= y and y < W);
return A[x][y];
}
};
#line 3 "/Users/korogi/Desktop/cp-cpp/util/rnd.hpp"
namespace rnd {
u32 seed; mt19937 mt;
struct gen_seed { gen_seed() { seed = random_device()(); mt = mt19937(seed); } } gen_seed_instance;
// [L, R)
template < class Int > Int i(Int L, Int R) { assert(L < R); return uniform_int_distribution<Int>(L, R - 1)(mt); }
template < class Real > Real r(Real L, Real R) { assert(L <= R); return uniform_real_distribution<Real>(L, R)(mt); }
}
template < int n, array<u32, n> mod > struct hash_vector {
array<u32, n> a;
using hvec = hash_vector;
hvec& s(array<u32, n> a) { FOR(i, n) this->a[i] = a[i] < mod[i] ? a[i] : a[i] - mod[i]; return *this; }
hash_vector(u32 v = 0) { FOR(i, n) a[i] = v % mod[i] + mod[i]; s(a); }
hvec operator - () const { return hvec() - *this; }
hvec& operator += (const hvec& r) { FOR(i, n) a[i] += r.a[i]; return s(a); }
hvec& operator -= (const hvec& r) { FOR(i, n) a[i] += mod[i] - r.a[i]; return s(a); }
hvec& operator *= (const hvec& r) { FOR(i, n) a[i] = u64(a[i]) * r.a[i] % mod[i]; return *this; }
hvec& operator /= (const hvec& r) { return *this *= inv(r); }
hvec operator + (const hvec& r) const { return hvec(*this) += r; }
hvec operator - (const hvec& r) const { return hvec(*this) -= r; }
hvec operator * (const hvec& r) const { return hvec(*this) *= r; }
hvec operator / (const hvec& r) const { return hvec(*this) /= r; }
bool operator == (const hvec& r) const { return a == r.a; }
bool operator != (const hvec& r) const { return a != r.a; }
bool operator < (const hvec& r) const { return a < r.a; }
};
template < int n, array<u32, n> mod > hash_vector<n, mod> pow(hash_vector<n, mod> x, u64 m) {
hash_vector<n, mod> p(1);
for(; m; m >>= 1) { if(m & 1) p *= x; x *= x; }
return p;
}
template < int n, array<u32, n> mod > hash_vector<n, mod> inv(hash_vector<n, mod> x) {
hash_vector<n, mod> res;
FOR(i, n) {
u32 a = x.a[i], b = mod[i], u = 1, v = 0;
while(b) { u32 t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }
res[i] = u;
}
return res;
}
template < int n, array<u32, n> mod > ostream& operator << (ostream& os, const hash_vector< n, mod >& x) { FOR(i, n) { if(i) os << ' '; os << x.a[i]; } return os; }
using hvec1 = hash_vector< 1, array<u32, 1>{999999937} >;
using hvec2 = hash_vector< 2, array<u32, 2>{999999937, 1000000007} >;
using hvec3 = hash_vector< 3, array<u32, 3>{999999937, 1000000007, 1000000009} >;
using hvec4 = hash_vector< 4, array<u32, 4>{999999937, 1000000007, 1000000009, 1000000021} >;
#line 184 "/Users/korogi/Desktop/cp-cpp/template.hpp"
namespace r52 {
int abs(int x) { return x >= 0 ? x : -x; }
i64 abs(i64 x) { return x >= 0 ? x : -x; }
i128 abs(i128 x) { return x >= 0 ? x : -x; }
}
#line 2 "/Users/korogi/Desktop/cp-cpp/ds/lazytree.hpp"
template < class A > struct lazytree {
using V = typename A::value_structure;
using T = typename V::value_type;
using O = typename A::operator_structure;
using F = typename O::value_type;
int n, sz, lg;
vector< T > a;
vector< F > lz;
int ce2(int n) {
int x = 0;
while((1 << x) < n) x++;
return x;
}
void update(int k) {
a[k] = V::op(a[2 * k], a[2 * k + 1]);
}
void all_apply(int k, F f) {
a[k] = A::op(a[k], f);
if(k < sz) lz[k] = O::op(lz[k], f);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = O::e();
}
lazytree() : lazytree(0) {}
lazytree(int n) : lazytree(vector< T >(n, V::e())) {}
lazytree(int n, T x) : lazytree(vector< T >(n, x)) {}
lazytree(const vector< T >& a_) : n(ssize(a_)) {
lg = ce2(n);
sz = 1 << lg;
a = vector< T >(sz + sz, V::e());
lz = vector< F >(sz, O::e());
FOR(i, n) a[sz + i] = a_[i];
REV(i, 1, sz) update(i);
}
void set(int i, T x) {
assert(0 <= i and i < n);
i += sz;
REV(p, 1, lg + 1) push(i >> p);
a[i] = x;
FOR(p, 1, lg + 1) update(i >> p);
}
T v(int i) {
assert(0 <= i and i < n);
i += sz;
REV(p, 1, lg + 1) push(i >> p);
return a[i];
}
T v(int l, int r) {
assert(0 <= l and l <= r and r <= n);
if(l == r) return V::e();
l += sz, r += sz;
REV(i, 1, lg + 1) {
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push((r - 1) >> i);
}
T sl = V::e(), sr = V::e();
while(l < r) {
if(l & 1) sl = V::op(sl, a[l++]);
if(r & 1) sr = V::op(a[--r], sr);
l >>= 1, r >>= 1;
}
return V::op(sl, sr);
}
T av() { return a[1]; }
void o(int i, F f) {
assert(0 <= i and i < n);
i += sz;
REV(p, 1, lg + 1) push(i >> p);
a[i] = A::op(a[i], f);
FOR(p, 1, lg + 1) update(i >> p);
}
void o(int l, int r, F f) {
assert(0 <= l and l <= r and r <= n);
if(l == r) return;
l += sz, r += sz;
REV(i, 1, lg + 1) {
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(i, 1, lg + 1) {
if(((l >> i) << i) != l) update(l >> i);
if(((r >> i) << i) != r) update((r - 1) >> i);
}
}
template < class G > int max_right(int l, G g) {
assert(0 <= l and l <= n);
assert(g(V::e()));
if(l == n) return n;
l += sz;
REV(i, 1, lg + 1) push(l >> i);
T s = V::e();
do {
while(l % 2 == 0) l >>= 1;
if(not g(V::op(s, a[l]))) {
while(l < sz) {
push(l);
l = 2 * l;
if(g(V::op(s, a[l]))) {
s = V::op(s, a[l]);
l++;
}
}
return l - sz;
}
s = V::op(s, a[l]);
l++;
} while((l & -l) != l);
return n;
}
template < class G > int min_left(int r, G g) {
assert(0 <= r and r <= n);
if(r == 0) return 0;
r += sz;
REV(i, 1, lg + 1) push((r - 1) >> i);
T s = V::e();
do {
r--;
while(r > 1 && (r % 2)) r >>= 1;
if(not g(V::op(a[r], s))) {
while(r < sz) {
push(r);
r = 2 * r + 1;
if(g(V::op(a[r], s))) {
s = V::op(a[r], s);
r--;
}
}
return r + 1 - sz;
}
s = V::op(a[r], s);
} while((r & -r) != r);
return 0;
}
};
#line 3 "/Users/korogi/Desktop/cp-cpp/alg/sum.hpp"
namespace alg {
template < class T > struct sum {
using value_type = T;
static constexpr T op(const T& a, const T& b) { return a + b; }
static constexpr T e() { return T(0); }
static constexpr T inv(const T& a) { return -a; }
static constexpr bool comm() { return true; }
};
}
#line 2 "/Users/korogi/Desktop/cp-cpp/alg/with_size.hpp"
namespace alg {
template < class M, class Int > struct with_size {
struct A {
using V = typename M::value_type;
mutable V value;
Int size;
};
using value_type = A;
static constexpr A op(const A& l, const A& r) { return A{M::op(l.value, r.value), l.size + r.size}; }
static constexpr A e() { return A{M::e(), 0}; }
};
}
#line 3 "/Users/korogi/Desktop/cp-cpp/alg/set.hpp"
namespace alg {
template < class T, T none = T(-1) > struct set_m {
using value_type = T;
static constexpr T op(const T& l, const T& r) { return r == none ? l : r; }
static constexpr T e() { return none; }
};
}
#line 5 "/Users/korogi/Desktop/cp-cpp/alg/range_set_range_sum.hpp"
// {x, 1} に初期化が必要
namespace alg {
template < class T, T none = T(-1) > struct range_set_range_sum {
using value_structure = with_size< sum< T >, int >;
using operator_structure = set_m< T, none >;
using S = typename value_structure::value_type;
using F = typename operator_structure::value_type;
static constexpr S op(const S& x, const F& f) {
if(f != none) x.value = f * x.size;
return x;
}
};
}
#line 2 "/Users/korogi/Desktop/cp-cpp/ds/set64.hpp"
// 参考: https://judge.yosupo.jp/submission/170327 by maspy
struct set64 {
static constexpr u32 B = 64;
int n, lg;
vector<vector<u64>> a;
set64() {}
set64(int n) : n(n) {
do { a.emplace_back(n = (n + B - 1) / B); } while(n > 1);
lg = ssize(a);
}
// i in S <=> b[i] = 1
set64(const vector<int>& b) : set64(ssize(b)) {
FOR(i, n) a[0][i / B] |= u64(b[i]) << (i % B);
FOR(h, lg - 1) FOR(i, ssize(a[h])) {
a[h + 1][i / B] |= u64(bool(a[h][i])) << (i % B);
}
}
void insert(int i) {
assert(0 <= i and i < n);
FOR(h, lg) a[h][i / B] |= u64(1) << (i % B), i /= B;
}
void erase(int i) {
assert(0 <= i and i < n);
u64 x = 0;
FOR(h, lg) {
a[h][i / B] &= ~(u64(1) << (i % B));
a[h][i / B] |= x << (i % B);
x = bool(a[h][i / B]);
i /= B;
}
}
bool contains(int i) {
return a[0][i / B] >> (i % B) & 1;
}
int next(int i) {
assert(i <= n);
chmax(i, 0);
FOR(h, lg) {
if(i / B == ssize(a[h])) break;
u64 d = a[h][i / B] >> (i % B);
if(!d) { i = i / B + 1; continue; }
i += bit::low(d);
REV(g, h) {
i *= B;
i += bit::low(a[g][i / B]);
}
return i;
}
return n;
}
int prev(int i) {
assert(-1 <= i);
if(n <= i) i = n - 1;
FOR(h, lg) {
if(i == -1) break;
u64 d = a[h][i / B] << (63 - i % B);
if(!d) { i = i / B - 1; continue; }
i -= __builtin_clzll(d);
REV(g, h) {
i *= B;
i += bit::top(a[g][i / B]);
}
return i;
}
return -1;
}
};
#line 3 "/Users/korogi/Desktop/cp-cpp/ds/interval.hpp"
template < class Key, class Value > struct DIU {
static constexpr Key MIN = -infty<Key>;
static constexpr Key MAX = +infty<Key>;
Value NONE;
// 区間の個数
int size;
// 区間の長さの合計
Key len;
map<Key, Value> mp;
DIU(Value NONE) : NONE(NONE), size(0), len(0) {
mp[MIN] = mp[MAX] = NONE;
}
// x in [l, r) -> v
tuple<Key, Key, Value> get(Key x, bool erase = false) {
auto itr = mp.upper_bound(x);
auto [r, vr] = *itr;
auto [l, vl] = *prev(itr);
if(vl != NONE and erase) {
size -= 1;
len -= r - l;
mp[l] = NONE;
merge(l);
merge(r);
}
return {l, r, vl};
}
// x 以上で最初に現れる NONE でない区間
// CODE FESTIVAL 2015 予選B D問題 (https://atcoder.jp/contests/code-festival-2015-qualb/tasks/codefestival_2015_qualB_d)
tuple<Key, Key, Value> get_next(Key x) {
auto it = mp.upper_bound(x);
auto p = prev(it);
if(p->second != NONE) {
return {max(x, p->first), it->first, p->second};
} else {
if(it->first == MAX) return {MAX, MAX, NONE}; // 存在しない場合
return {it->first, next(it)->first, it->second};
}
}
// x 以下で最初に現れる NONE でない区間
tuple<Key, Key, Value> get_prev(Key x) {
auto it = mp.upper_bound(x);
auto p = prev(it);
if (p->second != NONE) {
return {p->first, min(x + 1, it->first), p->second};
} else {
if (p->first == MIN) return {MIN, MIN, NONE}; // 存在しない場合
auto pp = prev(p);
return {pp->first, p->first, pp->second};
}
}
template < class F > void for_each_range(Key l, Key r, const F& f, bool erase = false) {
assert(MIN <= l and l <= r and r <= MAX);
if(erase) {
auto p = prev(mp.upper_bound(l));
if(p->first < l) {
mp[l] = p->second;
if(mp[l] != NONE) size += 1;
}
p = mp.lower_bound(r);
if(r < p->first) {
Value v = prev(p)->second;
mp[r] = v;
if(v != NONE) size += 1;
}
p = mp.lower_bound(l);
while(p->first < r) {
auto q = next(p);
Value v = p->second;
f(p->first, q->first, v);
if (v != NONE) size -= 1, len -= q->first - p->first;
p = mp.erase(p);
}
mp[l] = NONE;
} else {
auto itr = prev(mp.upper_bound(l));
while(itr->first < r) {
auto n_itr = next(itr);
f(max(itr->first, l), min(n_itr->first, r), itr->second);
itr = n_itr;
}
}
}
void set(Key l, Key r, Value v) {
assert(l <= r);
if(l == r) return;
for_each_range(l, r, [](Key l, Key r, Value v){}, true);
mp[l] = v;
if(v != NONE) size += 1, len += r - l;
merge(l);
merge(r);
}
template < class F > void for_all_range(const F& f, bool erase = false) {
for_each_range(MIN, MAX, f, erase);
}
private:
void merge(Key p) {
if(p == MIN or p == MAX) return;
auto itp = mp.lower_bound(p);
assert(itp->first == p);
auto itq = prev(itp);
if(itp->second == itq->second) {
if(itp->second != NONE) size -= 1;
mp.erase(itp);
}
}
};
/*
CF771(Div.2)-E
https://codeforces.com/contest/1638/problem/E
// 全体を -1 で初期化する
DIU<int, int> I(-1);
// [0, n) -> 0 の区間を追加する (初め a の色は 0)
I.set(0, n, 0);
// sum[c] := 色 c に足された値
vector<i64> sum(n, 0);
// a[i] = seg[i] + sum[a[i]->color] となるように管理する
lazytree<alg::range_add_range_min<i64>> seg(n, 0);
auto Q1 = [&] {
// 区間 [l, r) の色を c に変更する
I.for_each_range(l, r, [&](int l, int r, int c) { seg.o(l, r, sum[c]); }, true);
seg.o(l, r, -sum[c]);
I.set(l, r, c);
};
auto Q2 = [&]{
// 色が c の要素 a[i] に x を足す
sum[c] += x;
};
auto Q3 = [&]{
// a[i] を出力する
auto [l, r, c] = I.get(i);
print(sum[c] + seg.v(i));
};
オフラインの実装: https://codeforces.com/contest/1638/submission/347045852
*/
/*
ABC256-Ex I like Query Problem
https://atcoder.jp/contests/abc256/submissions/73026721
for_each_range() 内で直接書き換えるのではなく，
書き換えクエリを貯めておく．計算量は悪化しない．
*/
// [0, N) が小さい場合に高速．
template < class Value > struct DIU_o {
const int MIN, MAX;
Value NONE;
// 区間の個数
int size;
// 区間の長さの合計
int len;
vector<Value> dat;
set64 st;
DIU_o(int N, Value NONE) : MIN(0), MAX(N), NONE(NONE), size(0), len(0), dat(N, NONE), st(N) {
st.insert(0);
}
// x in [l, r) -> v
tuple<int, int, Value> get(int x, bool erase = false) {
int l = st.prev(x);
int r = st.next(x + 1);
Value v = dat[l];
if(v != NONE and erase) {
size -= 1;
len -= r - l;
dat[l] = NONE;
merge(l);
merge(r);
}
return {l, r, v};
}
// x 以上で最初に現れる NONE でない区間
tuple<int, int, Value> get_next(int x) {
if (x >= MAX) return {MAX, MAX, NONE};
int l = st.prev(x);
int r = st.next(x + 1);
if (dat[l] != NONE) {
return {max(x, l), r, dat[l]};
} else {
if (r >= MAX) return {MAX, MAX, NONE};
int nr = st.next(r + 1);
return {r, nr, dat[r]};
}
}
// x 以下で最初に現れる NONE でない区間
tuple<int, int, Value> get_prev(int x) {
if (x < MIN) return {MIN, MIN, NONE};
int l = st.prev(x);
int r = st.next(x + 1);
if (dat[l] != NONE) {
return {l, min(x + 1, r), dat[l]};
} else {
if (l <= MIN) return {MIN, MIN, NONE};
int pl = st.prev(l - 1);
return {pl, l, dat[pl]};
}
}
template < class F > void for_each_range(int l, int r, const F& f, bool erase = false) {
assert(MIN <= l and l <= r and r <= MAX);
if(l == r) return;
if(erase) {
int p = st.prev(l);
if(p < l) {
st.insert(l);
dat[l] = dat[p];
if(dat[l] != NONE) size += 1;
}
p = st.next(r);
if(r < p) {
dat[r] = dat[st.prev(r)];
st.insert(r);
if(dat[r] != NONE) size += 1;
}
p = l;
while(p < r) {
int q = st.next(p + 1);
Value v = dat[p];
f(p, q, v);
if(dat[p] != NONE) size -= 1, len -= q - p;
st.erase(p);
p = q;
}
st.insert(l);
dat[l] = NONE;
} else {
int i = st.prev(l);
while(i < r) {
int ni = st.next(i);
f(max(i, l), min(ni, r), dat[i]);
i = ni;
}
}
}
void set(int l, int r, Value v) {
if(l == r) return;
for_each_range(l, r, [](int l, int r, Value v){}, true);
st.insert(l);
dat[l] = v;
if(v != NONE) size += 1, len += r - l;
merge(l);
merge(r);
}
template < class F > void for_all_range(const F& f, bool erase = false) {
for_each_range(MIN, MAX, f, erase);
}
private:
void merge(int p) {
if(p <= MIN or MAX <= p) return;
int q = st.prev(p - 1);
if(dat[p] == dat[q]) {
if(dat[p] != NONE) size -= 1;
st.erase(p);
}
}
};
#line 2 "/Users/korogi/Desktop/cp-cpp/nt/kth_root_int.hpp"
// floor(a^{1/k})
// | 0 <= a < 2^64
// | 1 <= k
u64 kth_root(u64 a, u64 k) {
if(a == 0) return 0;
if(k == 1) return a;
if(k >= 64) return 1;
const static u64 ub[] = { 0,
18446744073709551615ULL, 4294967295, 2642245, 65535, 7131, 1625, 565, 255,
138, 84, 56, 40, 30, 23, 19, 15,
13, 11, 10, 9, 8, 7, 6, 6,
5, 5, 5, 4, 4, 4, 4, 3,
3, 3, 3, 3, 3, 3, 3, 3,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 1
};
if(k == 2) { for(u64 x = min<u64>(sqrtl(a), ub[2]); ; x--) if(x * x <= a) return x; }
if(k == 3) { for(u64 x = min<u64>(cbrtl(a), ub[3]); ; x--) if(x * x * x <= a) return x; }
const static auto pow = [](u64 x, u64 e) -> u64 {
u64 res = 1;
for(u64 i = 0; i < e; i++) res *= x;
return res;
};
u64 l = 0, r = ub[k] + 1;
while(l + 1 < r) {
u64 m = (l + r) / 2;
(pow(m, k) <= a ? l : r) = m;
}
return l;
}
#line 6 "a.cpp"
int main() {
int N = in(), Q = in();
vector<int> A = in(N);
using seg_type = alg::range_set_range_sum<i64>;
vector<seg_type::value_structure::value_type> seg_init(N);
FOR(i, N) seg_init[i] = {A[i], 1};
lazytree<seg_type> seg(seg_init);
DIU_o<int> I(N, -1);
FOR(i, N) I.set(i, i + 1, A[i]);
vector<tuple<int, int, int>> upd;
FOR(Q) {
int t = in();
if(t == 0) {
int L = in(), R = in();
print(seg.v(L, R).value);
} else if(t == 1) {
int L = in(), R = in(), X = in();
I.set(L, R, X);
seg.o(L, R, X);
} else {
int L = in(), R = in();
upd.clear();
I.for_each_range(L, R, [&](int l, int r, int v) {
const int nv = kth_root(v, 2);
seg.o(l, r, nv);
upd.push_back({l, r, nv});
}, true);
for(auto [l, r, v] : upd) I.set(l, r, v);
}
}
}