//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
//#define int long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, q, k;
int a[nmax];
struct Seg{
pii tree[1 << 18];
void build(int id, int l, int r){
if(l == r){
tree[id]= {a[l], a[l]};
return;
}
int mid = r + l >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
}
void update_1(int id, int l, int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
tree[id].fi = val;
tree[id].se = val;
return;
}
int mid = r + l >> 1;
update_1(id << 1, l, mid, u, val);
update_1(id << 1 | 1, mid + 1, r, u, val);
tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
}
void update_2(int id, int l, int r, int u, int v){
if(l > v || r < u || u > v || tree[id].se == 0) return;
if(l == r){
tree[id].fi = tree[id].se = tree[id].fi / k;
return;
}
int mid = r + l >> 1;
update_2(id << 1, l, mid,u, v);
update_2(id << 1 | 1, mid + 1, r, u, v);
tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
}
ll get(int id, int l, int r, int u, int v){
if(l >= u && r <= v) return tree[id].fi;
int mid = r + l >> 1;
if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
if(mid + 1 > v) return get(id << 1, l, mid, u, v);
return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
}tree;
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> q >> k;
for(int i = 1; i <= n; ++i) cin >> a[i];
tree.build(1, 1, n);
while(q--){
int t, x, y;
cin >> t >> x >> y;
if(t == 1){
tree.update_1(1, 1, n, x, y);
}
else if(t == 2){
tree.update_2(1, 1, n, x, y);
}
else cout << tree.get(1, 1, n, x, y) << endl;
// for(int i = 1; i <= n; ++i) cout << tree.get(1, 1, n, i, i) << ' ';
// cout << endl;
}
}
/*
9 4 23 9
5
12 27 14 30
8 19 8 9
6 21 5 7
1 4 4 29
11 20 11 12
*/
Compilation message
sterilizing.cpp: In member function 'void Seg::build(int, int, int)':
sterilizing.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid = r + l >> 1;
| ~~^~~
sterilizing.cpp: In member function 'void Seg::update_1(int, int, int, int, int)':
sterilizing.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = r + l >> 1;
| ~~^~~
sterilizing.cpp: In member function 'void Seg::update_2(int, int, int, int, int)':
sterilizing.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = r + l >> 1;
| ~~^~~
sterilizing.cpp: In member function 'long long int Seg::get(int, int, int, int, int)':
sterilizing.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = r + l >> 1;
| ~~^~~
sterilizing.cpp: At global scope:
sterilizing.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1928 ms |
4760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3068 KB |
Output is correct |
| 4 |
Correct |
25 ms |
3932 KB |
Output is correct |
| 5 |
Correct |
28 ms |
4176 KB |
Output is correct |
| 6 |
Correct |
28 ms |
4200 KB |
Output is correct |
| 7 |
Execution timed out |
5072 ms |
4308 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
