/*
Idea:
Represent C[i] in base K.
Seg:
Each node will save the representation in base K as a vector with the sum of values in each power.
Merging is in O(log) by adding the vectors.
Operation 1 is a point update changing the vector of a leaf node and recalculating the ancestors.
Operation 2 is a lazy range update that will make seg[pos][i] = segp[pos][i + 1]
Operation 3 is a range query by merging of range nodes and then computing the final value.
O(Qlog(N)^2)
Confidence 7/10
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10;
int n, q, k;
int v[MAXN];
vector<int> seg[4 * MAXN];
int lz[4 * MAXN];
void refresh(int pos, int ini, int fim);
void build(int pos, int ini, int fim);
void updatePoint(int pos, int ini, int fim, int id, int val);
void updateRange(int pos, int ini, int fim, int p, int q);
vector<int> query(int pos, int ini, int fim, int p, int q);
void merge(vector<int>& ret, vector<int>& e, vector<int>& d);
long long unconv(vector<int> val);
void conv(vector<int>& ret, int val);
int main() {
scanf("%d %d %d", &n, &q, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
assert(k != 1);
build(1, 1, n);
// for(int i = 1; i <= n; i++) {
// vector<int> aux = query(1, 1, n, i, i);
// printf("%lld (", unconv(aux));
// for(int j = 4; j >= 0; j--) {
// printf("%d ", aux[j]);
// }
// printf(")");
// }
// printf("\n");
for(int i = 1; i <= q; i++) {
int s, a, b;
scanf("%d %d %d", &s, &a, &b);
if(s == 1) {
updatePoint(1, 1, n, a, b);
}
if(s == 2) {
if(k != 1) updateRange(1, 1, n, a, b);
}
if(s == 3) {
vector<int> aux = query(1, 1, n, a, b);
long long ans = unconv(aux);
printf("%lld\n", ans);
}
// for(int i = 1; i <= n; i++) {
// vector<int> aux = query(1, 1, n, i, i);
// printf("%lld (", unconv(aux));
// for(int j = 4; j >= 0; j--) {
// printf("%d ", aux[j]);
// }
// printf(")");
// }
// printf("\n");
}
}
void refresh(int pos, int ini, int fim) {
if(lz[pos] == 0) return;
if(k == 1) return;
for(int i = 0; i < seg[pos].size(); i++) {
if(i + lz[pos] >= seg[pos].size()) seg[pos][i] = 0;
else seg[pos][i] = seg[pos][i + lz[pos]];
}
if(ini != fim) {
int e = pos << 1, d = e | 1;
lz[e] += lz[pos];
lz[d] += lz[pos];
}
lz[pos] = 0;
}
void build(int pos, int ini, int fim) {
if(ini == fim) {
conv(seg[pos], v[ini]);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
build(e, ini, mid);
build(d, mid + 1, fim);
merge(seg[pos], seg[e], seg[d]);
}
void updatePoint(int pos, int ini, int fim, int id, int val) {
refresh(pos, ini, fim);
if(ini > id || fim < id) return;
if(ini == fim) {
conv(seg[pos], val);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
updatePoint(e, ini, mid, id, val);
updatePoint(d, mid + 1, fim, id, val);
merge(seg[pos], seg[e], seg[d]);
}
void updateRange(int pos, int ini, int fim, int p, int q) {
refresh(pos, ini, fim);
if(ini > q || fim < p) return;
if(ini >= p && fim <= q) {
lz[pos]++;
refresh(pos, ini, fim);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
updateRange(e, ini, mid, p, q);
updateRange(d, mid + 1, fim, p, q);
merge(seg[pos], seg[e], seg[d]);
}
vector<int> query(int pos, int ini, int fim, int p, int q) {
refresh(pos, ini, fim);
if(ini > q || fim < p) return vector<int> (35);
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
vector<int> eVal = query(e, ini, mid, p, q);
vector<int> dVal = query(d, mid + 1, fim, p, q);
vector<int> ret;
merge(ret, eVal, dVal);
return ret;
}
void merge(vector<int>& ret, vector<int>& e, vector<int>& d) {
ret = vector<int> (e.size());
for(int i = 0; i < e.size(); i++) {
ret[i] = e[i] + d[i];
}
}
long long unconv(vector<int> val) {
long long ret = 0;
for(int i = val.size() - 1; i >= 0; i--) {
ret *= k;
ret += val[i];
}
return ret;
}
void conv(vector<int>& ret, int val){
ret = vector<int> (35);
if(val == 0) return;
int aux = 0;
if(k == 1) ret[aux] = val, val = 0;
while(val > 0) {
ret[aux] = val % k;
val /= k;
aux++;
}
}
Compilation message
sterilizing.cpp: In function 'void refresh(int, int, int)':
sterilizing.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < seg[pos].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | if(i + lz[pos] >= seg[pos].size()) seg[pos][i] = 0;
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'void merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
sterilizing.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i = 0; i < e.size(); i++) {
| ~~^~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d %d %d", &n, &q, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d", &v[i]);
| ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d %d %d", &s, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9684 KB |
Output is correct |
| 2 |
Runtime error |
12 ms |
19404 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
19864 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
11812 KB |
Output is correct |
| 2 |
Correct |
70 ms |
24404 KB |
Output is correct |
| 3 |
Correct |
108 ms |
24436 KB |
Output is correct |
| 4 |
Correct |
300 ms |
17792 KB |
Output is correct |
| 5 |
Correct |
529 ms |
42444 KB |
Output is correct |
| 6 |
Correct |
504 ms |
42496 KB |
Output is correct |
| 7 |
Runtime error |
18 ms |
20172 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
314 ms |
26624 KB |
Output is correct |
| 2 |
Correct |
320 ms |
26932 KB |
Output is correct |
| 3 |
Correct |
221 ms |
24572 KB |
Output is correct |
| 4 |
Correct |
330 ms |
20300 KB |
Output is correct |
| 5 |
Correct |
538 ms |
42572 KB |
Output is correct |
| 6 |
Correct |
534 ms |
42672 KB |
Output is correct |
| 7 |
Correct |
518 ms |
42632 KB |
Output is correct |
| 8 |
Correct |
586 ms |
42748 KB |
Output is correct |
| 9 |
Correct |
406 ms |
42736 KB |
Output is correct |
| 10 |
Correct |
426 ms |
42700 KB |
Output is correct |
| 11 |
Correct |
352 ms |
42716 KB |
Output is correct |
| 12 |
Correct |
386 ms |
42820 KB |
Output is correct |
