結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 The Forsaking
|
| 提出日時 | 2026-04-18 01:59:29 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 623 ms / 2,000 ms |
| コード長 | 7,221 bytes |
| 記録 | |
| コンパイル時間 | 2,964 ms |
| コンパイル使用メモリ | 235,876 KB |
| 実行使用メモリ | 17,664 KB |
| 最終ジャッジ日時 | 2026-04-18 01:59:43 |
| 合計ジャッジ時間 | 10,109 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];
struct ST {
struct Node {
int l, r;
ll sum;
};
vector<Node> tr;
ST(const ST& other) : tr(other.tr) { }
ST(ST&& other) noexcept : tr(move(other.tr)) { }
ST (int l, int r) : tr(vector<Node>(((r - l + 1) << 2) + 10)) { build(1, l, r); }
ST& operator=(ST&& other) noexcept {
if (this != &other) {
tr = move(other.tr);
}
return *this;
}
ST& operator=(const ST& other) {
if (this != &other) {
tr = other.tr;
}
return *this;
}
void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; }
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
ll query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
ll res = 0;
if (l <= mid) res += query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
void modify(int u, int x, ll v) {
if (tr[u].l == tr[u].r) tr[u].sum += v;
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
if (x > mid) modify(u << 1 | 1, x, v);
pushup(u);
}
}
};
void solve() {
set<array<int, 3> > st;
scanf("%d%d", &n, &m);
for (int i = 1, x; i < n + 1; i++) {
scanf("%d", &x);
st.insert({i, 1, x});
}
ST tr(1, n);
for (auto u : st) tr.modify(1, u[0], u[2]);
while (m--) {
int op, l, r, x;
scanf("%d%d%d", &op, &l, &r);
++l;
if (op == 0) {
if (l > r) {
puts("0");
continue;
}
ll sum = tr.query(1, l, r);
auto u = st.lower_bound({l, -1, -1});
if (u != st.begin()) {
--u;
int v = (*u)[2], p = (*u)[0], c = (*u)[1];
if (p + c - 1 >= l) {
sum += min(p + c - l, r - l + 1) * (ll)v;
}
}
u = st.lower_bound({r + 1, -1, -1});
if (u != st.begin()) {
--u;
int v = (*u)[2], p = (*u)[0], c = (*u)[1];
if (p >= l && p + c - 1 > r) {
sum -= (p + c - 1 - r) * (ll)v;
}
}
printf("%lld\n", sum);
} else if (op == 1) {
scanf("%d", &x);
if (l > r) continue;
while (1) {
auto u = st.lower_bound({l, -1, -1});
if (u == st.end() || (*u)[0] > r) break;
auto t = *u;
tr.modify(1, t[0], -(ll)t[1] * t[2]);
st.erase(u);
if (t[0] + t[1] - 1 > r) {
t[1] -= r - t[0] + 1, t[0] = r + 1;
st.insert(t);
tr.modify(1, t[0], (ll)t[1] * t[2]);
}
}
auto u = st.lower_bound({l, -1, -1});
if (u != st.begin()) {
--u;
int v = (*u)[2], p = (*u)[0], c = (*u)[1];
if (p + c - 1 >= l) {
tr.modify(1, p, -(ll)v * c);
st.erase(u);
st.insert({p, l - p, v});
tr.modify(1, p, (ll)v * (l - p));
if (p + c - 1 > r) {
st.insert({r + 1, p + c - 1 - r, v});
tr.modify(1, r + 1, (ll)v * (p + c - 1 - r));
}
}
}
st.insert({l, r - l + 1, x});
tr.modify(1, l, (ll)(r - l + 1) * x);
} else {
if (l > r) continue;
vector<array<int, 3>> q;
while (1) {
auto u = st.lower_bound({l, -1, -1});
if (u == st.end() || (*u)[0] > r) break;
auto t = *u;
tr.modify(1, t[0], -(ll)t[1] * t[2]);
st.erase(u);
if (t[0] + t[1] - 1 > r) {
auto g = t;
g[1] -= r - g[0] + 1, g[0] = r + 1;
st.insert(g);
tr.modify(1, g[0], (ll)g[1] * g[2]);
}
t[1] = min(t[1], r - t[0] + 1), t[2] = sqrt(t[2]);
q.push_back(t);
tr.modify(1, t[0], (ll)t[1] * t[2]);
}
for (auto u : q) st.insert(u);
auto u = st.lower_bound({l, -1, -1});
if (u != st.begin()) {
--u;
int v = (*u)[2], p = (*u)[0], c = (*u)[1];
if (p + c - 1 >= l) {
array<int, 3> t = {l, min(r - l + 1, p + c - l), v};
tr.modify(1, p, -(ll)v * c);
st.erase(u);
st.insert({p, l - p, v});
tr.modify(1, p, (ll)v * (l - p));
if (p + c - 1 > r) {
st.insert({r + 1, p + c - 1 - r, v});
tr.modify(1, r + 1, (ll)v * (p + c - 1 - r));
}
t[2] = sqrt(t[2]);
st.insert(t);
tr.modify(1, t[0], (ll)t[1] * t[2]);
}
}
u = st.lower_bound({l, -1, -1});
if (u != st.begin()) --u;
while (u != st.end() && (*u)[0] <= r) {
while (1) {
auto t = u;
++t;
if (t != st.end() && ((*t)[2] == (*u)[2])) {
int v = (*t)[2], p = (*t)[0], c = (*t)[1];
tr.modify(1, p, (ll)-v * c);
st.erase(t);
auto g = *u;
tr.modify(1, g[0], -(ll)g[1] * g[2]);
st.erase(u);
g[1] += c;
u = st.insert(g).first;
tr.modify(1, g[0], (ll)g[1] * g[2]);
} else break;
}
++u;
}
}
}
}
void s2() {
scanf("%d%d", &n, &m);
for (int i = 1, x; i < n + 1; i++) {
scanf("%d", w + i);
}
while (m--) {
int op, l, r, x;
scanf("%d%d%d", &op, &l, &r);
++l;
if (op == 0) {
if (l > r) {
puts("0");
continue;
}
ll sum = 0;
for (int i = l; i <= r; i++) sum += w[i];
printf("%lld\n", sum);
} else if (op == 1) {
scanf("%d", &x);
if (l > r) continue;
for (int i = l; i <= r; i++) w[i] = x;
} else {
if (l > r) continue;
for (int i = l; i <= r; i++) w[i] = sqrt(w[i]);
}
}
}
int main() {
int T = 1;
// cin >> T;
// while (T--) s2();
while (T--) solve();
return 0;
}