// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
const int MOD = 1e9 + 7;
struct Node {
ll sum;
int mx;
Node() {};
Node(int val) : sum(val), mx(val) {};
Node(ll sum, int mx) : sum(sum), mx(mx) {};
Node operator+(const Node &other) const {
return Node(sum + other.sum, max(mx, other.mx));
};
};
int n, q, k;
int a[MAX_N + 5];
Node seg[4 * MAX_N + 5];
void build(int node, int l, int r) {
if (l == r) {
seg[node] = Node(a[l]);
return;
};
int mid = (l + r) >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
seg[node] = seg[node << 1] + seg[node << 1 | 1];
};
void updatePos(int pos, int val) {
int l = 1, r = n, node = 1;
while (l < r) {
int mid = (l + r) >> 1;
if (pos <= mid) {
node <<= 1;
r = mid;
} else {
(node <<= 1) |= 1;
l = mid + 1;
};
};
seg[node] = Node(val);
while (node > 1) {
node >>= 1;
seg[node] = seg[node << 1] + seg[node << 1 | 1];
};
};
void updateRange(int node, int l, int r, int u, int v) {
if (l > v || r < u) return;
if (seg[node].mx == 0) return;
if (l >= u && r <= v) {
seg[node].sum /= k;
seg[node].mx /= k;
};
if (l == r) return;
int mid = (l + r) >> 1;
updateRange(node << 1, l, mid, u, v);
updateRange(node << 1 | 1, mid + 1, r, u, v);
seg[node] = seg[node << 1] + seg[node << 1 | 1];
};
void updateRange(int l, int r) {
updateRange(1, 1, n, l, r);
};
ll get(int node, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return seg[node].sum;
int mid = (l + r) >> 1;
return get(node << 1, l, mid, u, v) + get(node << 1 | 1, mid + 1, r, u, v);
};
ll get(int l, int r) {
return get(1, 1, n, l, r);
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen("MAIN.INP", "r")) {
freopen("MAIN.INP", "r", stdin);
freopen("MAIN.OUT", "w", stdout);
};
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
};
build(1, 1, n);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int pos, val;
cin >> pos >> val;
updatePos(pos, val);
} else {
int l, r;
cin >> l >> r;
if (type == 3) {
cout << get(l, r) << '\n';
} else {
if (k != 1) updateRange(l, r);
};
};
};
};
Compilation message (stderr)
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen("MAIN.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen("MAIN.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |