結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー 👑 sgfc
提出日時 2026-04-18 00:54:51
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 6,519 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,795 ms
コンパイル使用メモリ 676,172 KB
実行使用メモリ 198,868 KB
最終ジャッジ日時 2026-04-18 00:55:44
合計ジャッジ時間 16,499 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3")

//import std;
#include "bits/stdc++.h"
#include <stdio.h>
#include "atcoder/all"
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

using namespace std;
using namespace atcoder;

using ll = long long;
using ull = unsigned long long;
using mint = modint998244353;
using mint2 = modint1000000007;
const double eps = 1e-9;

#define OVERLOAD3(_1, _2, _3, call,...) call
#define REP1(i, n) for (ll i = 0; i < ll(n); ++i)
#define REP2(i, a, b) for (ll i = ll(a); i < ll(b); ++i)
#define REP(...) OVERLOAD3(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define RREP1(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define RREP2(i, a, b) for (ll i = ll(a) - 1; i >= b; --i)
#define RREP(...) OVERLOAD3(__VA_ARGS__, RREP2, RREP1)(__VA_ARGS__)
#define REPE(i, c) for (auto&& i : c)
#define TCASE() ll _ttt; cin >> _ttt; while(_ttt--)

using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vb = vector<bool>;
using vd = vector<double>; using pl = pair<ll, ll>; using vpl = vector<pl>; using vvpl = vector<vpl>;

template<class T> void sc(T& x) { string s; if (cin >> s) from_chars(s.data(), s.data() + s.size(), x); }
template<> void sc(string& x) { cin >> x; }
template<class... T> void COMMON_IN(T&... a) { (sc(a), ...); }
#define LI(...) ll __VA_ARGS__; COMMON_IN(__VA_ARGS__);
#define SI(...) string __VA_ARGS__; COMMON_IN(__VA_ARGS__);
#define VLI(a, n) vector<ll> a(n); for(auto& x : a) sc(x);
#define DLI(a, n) deque<ll> a(n); for(auto& x : a) sc(x);
#define VSI(a, n) vector<string> a(n); for(auto& x : a) cin >> x;
#define VVLI(a, n, m) vector<vector<ll>> a(n, vector<ll>(m)); for(auto& x : a) for(auto& y : x) sc(y);
struct uv { ll u; ll v; }; struct uvc { ll u; ll v; ll c = 1; };
#define VUVI(a, n) vector<uv> a; a.assign(n, {0, 0}); for(auto& x : a) {sc(x.u); sc(x.v); x.u--; x.v--;}
#define VUVCI(a, n) vector<uvc> a; a.assign(n, {0, 0, 0}); for(auto& x : a) {sc(x.u); sc(x.v); sc(x.c); x.u--; x.v--;}

vvl to_edge(const ll n, const vector<uv>& v) { vvl ret(n); for (auto& x : v) ret[x.u].emplace_back(x.v); return ret; }
vvl to_edge_d(const ll n, const vector<uv>& v) { vvl ret(n); for (auto& x : v) { ret[x.u].emplace_back(x.v); ret[x.v].emplace_back(x.u); } return ret; }
vvpl to_edge(const ll n, const vector<uvc>& v) { vvpl ret(n); for (auto& x : v) { ret[x.u].emplace_back(x.v, x.c); } return ret; }
vvpl to_edge_d(const ll n, const vector<uvc>& v) { vvpl ret(n); for (auto& x : v) { ret[x.u].emplace_back(x.v, x.c); ret[x.v].emplace_back(x.u, x.c); } return ret; }

template <class T = long long> using pql = priority_queue<T>;
template <class T = long long> using pqg = priority_queue<T, vector<T>, greater<T>>;
using vm = vector<mint>; using vvm = vector<vm>;

template <class T> requires std::is_base_of_v<atcoder::internal::modint_base, T> ostream& operator<<(ostream& os, const T& v) { os << v.val(); return os; }
void yn(bool f) { std::cout << (f ? "Yes" : "No") << "\n"; };
template<class T> void ovn(const T& v) { for (auto it = v.begin(); it != v.end(); it++) { if (it != v.begin()) cout << " "; cout << *it; }  cout << "\n"; };

const ll llhuge = 1LL << 61; //十分でかいが多少足しても溢れない数値
auto gmax(const auto& a, const auto& b) { return a > b ? a : b; };
auto gmin(const auto& a, const auto& b) { return a < b ? a : b; };
bool chmin(auto& a, const auto& b) { const auto olda = a; a = gmin(a, b); return olda != a; }
bool chmax(auto& a, const auto& b) { const auto olda = a; a = gmax(a, b); return olda != a; }
void sort(auto& v) { std::ranges::sort(v); };
void rev(auto& v) { std::ranges::reverse(v); };
template<class T, class K = T::key_type, class V = T::mapped_type> [[nodiscard]] V myat(const T& mp, const K& key) { return mp.find(key) == mp.end() ? V() : mp.at(key); }
long long ceil(const long long a, const long long b) { return (a + b - 1) / b; }
template<class T, class U> pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) { return { a.first + b.first, a.second + b.second }; }


//sqrtの切り捨て、切り上げ
unsigned long long _floor_sqrt(unsigned long long n) {
	if (n == 0) return 0;
	if (n <= 3) return 1;
	unsigned long long x = (unsigned long long)floor(sqrt((long double)n));
	while ((x + 1) <= n / (x + 1)) ++x;
	while (x > n / x) --x;
	return x;
}

vl mp(1000000, -1);
unsigned long long floor_sqrt(unsigned long long n) {
	if (n < mp.size()) return mp[n];
	return _floor_sqrt(n);
}

//区間更新, 区間count,SUM
using S = pair<ll, ll>;
using F = ll;
S op(S l, S r) {
	return { l.first + r.first, l.second + r.second };
}
S e() { return { 0, 0 }; }
S mapping(F l, S r) { return l == llhuge ? r : S{ r.first, l * r.second }; }
F composition(F l, F r) { return r; }
F id() { return llhuge; }
using lst = lazy_segtree<S, op, e, F, mapping, composition, id>;

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

	for (int i = 0; i * i < mp.size(); i++) {
		mp[i * i] = i;
	}
	REP(i, mp.size()) {
		if (mp[i] == -1) mp[i] = mp[i - 1];
	}

	LI(n, q);

	vector segs(31, lst());
	vector<pl> init(n);
	VLI(a, n);
	REP(i, n) init[i] = { 1, a[i] };
	REP(j, 31) {
		segs[j] = lst(init);
		REP(i, n) {
			init[i].second = floor_sqrt(init[i].second);
		}
	}

	ll qb = floor_sqrt(q);
	ll qs = (q + qb - 1) / qb;
	set<ll> br;
	fenwick_tree<ll> fw(n+1);

	REP(i, q) {
		if (i % qs == 0) {
			vector<pl> init_n(n);
			REP(i, n) {
				ll v = segs[0].get(i).second;
				ll lp = fw.sum(0, i + 1);
				REP(x, lp) v = floor_sqrt(v);
				init_n[i] = { 1, v };
			}
			REP(j, 31) {
				segs[j] = lst(init_n);
				REP(i, n) {
					init_n[i].second = floor_sqrt(init_n[i].second);
				}
			}
			br = set<ll>();
			br.insert(0);
			br.insert(n);
			fw = fenwick_tree<ll>(n+1);
		}

		LI(t, l, r);
		if (t == 0) {
			ll ans = 0;
			auto it = br.upper_bound(l);
			it--;
			while (*it < r) {
				ll nv = *next(it);
				ll rl = max(l, *it);
				ll rr = min(r, nv);
				ll off = min(fw.sum(0, *it + 1), 30LL);
				ans += segs[off].prod(rl, rr).second;
				it++;
			}
			cout << ans << "\n";
		}
		if (t == 1) {
			LI(x);
			ll oldr = fw.sum(0, r);
			REP(j, 31) {
				segs[j].apply(l, r, x);
				x = floor_sqrt(x);
			}
			auto it = br.upper_bound(l);
			it--;
			while (it != br.end() && *it < r) {
				fw.add(*it, fw.sum(*it, *it + 1) * -1);
				it = br.erase(it);
			}

			ll oldl = fw.sum(0, l);
			fw.add(l, oldl * -1);
			fw.add(r, oldr);
			br.insert(l);
			br.insert(r);
		}
		if (t == 2) {
			br.insert(l);
			br.insert(r);
			fw.add(l, 1);
			fw.add(r, -1);
		}
	}
}
0