結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 The Forsaking
|
| 提出日時 | 2026-04-18 01:14:57 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,040 bytes |
| 記録 | |
| コンパイル時間 | 1,749 ms |
| コンパイル使用メモリ | 233,100 KB |
| 実行使用メモリ | 25,472 KB |
| 最終ジャッジ日時 | 2026-04-18 01:15:52 |
| 合計ジャッジ時間 | 8,994 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 28 |
ソースコード
#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) {
if (l > r) continue;
scanf("%d", &x);
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);
c = l - p;
st.insert({p, c, v});
tr.modify(1, p, (ll)v * c);
}
}
st.insert({l, r - l + 1, x});
tr.modify(1, l, (ll)(r - l + 1) * x);
} else {
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) {
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]);
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) {
array<int, 3> t = {l, p + c - l, v};
tr.modify(1, p, -(ll)v * c);
st.erase(u);
c = l - p;
st.insert({p, c, v});
tr.modify(1, p, (ll)v * c);
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;
}
}
}
}
int main() {
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}