#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int INF = 1e17;
const int MOD = 1e9;
struct SegTree {
vector<deque<int>> values;
vector<int> operations;
int size, k;
void init(int n, int _k) {
size = 1; k = _k;
while (size < n) size <<= 1;
operations.resize(2*size);
values.resize(2*size);
}
void propogate(int x, int lx, int rx) {
if (rx - lx != 1) {
operations[2*x+1] += operations[x];
operations[2*x+2] += operations[x];
}
for ( ; operations[x] && values[x].size() > 1; operations[x]--) values[x].pop_front();
operations[x] = 0;
}
void update(int x, int lx, int rx) {
if (rx - lx == 1) return;
int m = (lx + rx) >> 1;
while (values[x].size() > 0) values[x].pop_front();
propogate(2*x+1, lx, m);
propogate(2*x+2, m, rx);
int i, j;
for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
values[x].push_back(values[2*x+1][i] + values[2*x+2][j]);
}
for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
}
void set(int i, int v, int x, int lx, int rx) {
propogate(x, lx, rx);
if (rx - lx == 1) {
while (values[x].size() > 0) values[x].pop_front();
while (v) {
values[x].push_back(v); v /= k;
}
values[x].push_back(v);
return;
}
int m = (lx + rx) >> 1;
if (i < m) set(i, v, 2*x+1, lx, m);
else set(i, v, 2*x+2, m, rx);
update(x, lx, rx);
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
void modify(int l, int r, int x, int lx, int rx) {
propogate(x, lx, rx);
if (lx >= r || l >= rx) return;
if (l <= lx && rx <= r) return void(operations[x]++);
int m = (lx + rx) >> 1;
modify(l, r, 2*x+1, lx, m);
modify(l, r, 2*x+2, m, rx);
update(x, lx, rx);
}
void modify(int l, int r) {
modify(l, r, 0, 0, size);
}
int calc(int l, int r, int x, int lx, int rx) {
propogate(x, lx, rx);
if (lx >= r || l >= rx) return 0;
if (l <= lx && rx <= r) {
return values[x].front();
}
int m = (lx + rx) >> 1;
int s1 = calc(l, r, 2*x+1, lx, m);
int s2 = calc(l, r, 2*x+2, m, rx);
return s1 + s2;
}
int calc(int l, int r) {
return calc(l, r, 0, 0, size);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k; cin>>n>>m>>k;
SegTree st; st.init(n, k);
for (int i = 0; i < n; i++) {
int x; cin>>x;
st.set(i, x);
}
while (m--) {
int t, a, b; cin>>t>>a>>b;
if (t == 1) {
st.set(a-1, b);
} else if (t == 2 && k > 1) {
st.modify(a-1, b);
} else if (t == 3) {
cout<<st.calc(a-1, b)<<"\n";
}
}
}
Compilation message
sterilizing.cpp: In member function 'void SegTree::update(long long int, long long int, long long int)':
sterilizing.cpp:36:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:36:58: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
| ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
| ~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
492 KB |
Output is correct |
| 2 |
Runtime error |
993 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
900 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
11756 KB |
Output is correct |
| 2 |
Correct |
150 ms |
90296 KB |
Output is correct |
| 3 |
Correct |
172 ms |
90348 KB |
Output is correct |
| 4 |
Correct |
269 ms |
45420 KB |
Output is correct |
| 5 |
Correct |
564 ms |
180588 KB |
Output is correct |
| 6 |
Correct |
567 ms |
180972 KB |
Output is correct |
| 7 |
Runtime error |
554 ms |
524292 KB |
Execution killed with signal 9 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
512 ms |
90648 KB |
Output is correct |
| 2 |
Correct |
529 ms |
91444 KB |
Output is correct |
| 3 |
Correct |
694 ms |
92908 KB |
Output is correct |
| 4 |
Correct |
578 ms |
51308 KB |
Output is correct |
| 5 |
Correct |
898 ms |
180460 KB |
Output is correct |
| 6 |
Correct |
1010 ms |
181836 KB |
Output is correct |
| 7 |
Correct |
855 ms |
182252 KB |
Output is correct |
| 8 |
Correct |
1220 ms |
196204 KB |
Output is correct |
| 9 |
Correct |
917 ms |
198252 KB |
Output is correct |
| 10 |
Correct |
1037 ms |
196204 KB |
Output is correct |
| 11 |
Correct |
760 ms |
183856 KB |
Output is correct |
| 12 |
Correct |
1369 ms |
195088 KB |
Output is correct |
