#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<17)
#define _1 first
#define _2 second
struct SegTree {
P seg[MAX_N*2-1] = {};
long long sum[MAX_N*2-1] = {};
void update(int k, int v) {
k += MAX_N-1;
seg[k] = P(v, k-(MAX_N-1));
sum[k] = v;
while (k > 0) {
k = (k-1) / 2;
seg[k] = max(seg[k*2+1], seg[k*2+2]);
sum[k] = sum[k*2+1] + sum[k*2+2];
}
}
P query_max(int a, int b, int k=0, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return P(-1, -1);
if (a <= l && r <= b) return seg[k];
return max(query_max(a, b, k*2+1, l, (l+r)/2), query_max(a, b, k*2+2, (l+r)/2, r));
}
long long query_sum(int a, int b, int k=0, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return 0;
if (a <= l && r <= b) return sum[k];
return query_sum(a, b, k*2+1, l, (l+r)/2) + query_sum(a, b, k*2+2, (l+r)/2, r);
}
};
int N, Q, K;
SegTree seg;
int main() {
cin >> N >> Q >> K;
rep(i, N) {
int a;
cin >> a;
seg.update(i, a);
}
rep(i, Q) {
int t, l, r;
cin >> t >> l >> r;
l--, r--;
if (t == 1) {
r++;
seg.update(l, r);
}
else if (t == 2) {
queue<P> qs;
qs.push(P(l, r+1));
while (!qs.empty()) {
int l = qs.front()._1, r = qs.front()._2; qs.pop();
P p = seg.query_max(l, r);
int val = p._1, pos = p._2;
if (val <= 0) continue;
seg.update(pos, val/K);
if (l < pos) qs.push(P(l, pos));
if (pos+1 < r) qs.push(P(pos+1, r));
}
}
else {
cout << seg.query_sum(l, r+1) << "\n";
}
}
return 0;
}
Compilation message
Compilation timeout while compiling sterilizing
