#include <iostream> #include <vector> #include <algorithm> using namespace std; // Dùng long long vì tổng có thể vượt quá 2^31 typedef long long ll; const int MAXN = 100005; struct Node { ll sum; ll max_val; }; int N, Q; ll K; ll arr[MAXN]; Node tree[4 * MAXN]; // Hàm hợp nhất hai nút con Node merge(Node left, Node right) { Node res; res.sum = left.sum + right.sum; res.max_val = max(left.max_val, right.max_val); return res; } // Xây dựng cây void build(int node, int start, int end) { if (start == end) { tree[node].sum = arr[start]; tree[node].max_val = arr[start]; } else { int mid = (start + end) / 2; build(2 * node, start, mid); build(2 * node + 1, mid + 1, end); tree[node] = merge(tree[2 * node], tree[2 * node + 1]); } } // Thao tác 1: Cập nhật điểm (Point Update) void update_point(int node, int start, int end, int idx, ll val) { if (start == end) { tree[node].sum = val; tree[node].max_val = val; } else { int mid = (start + end) / 2; if (start <= idx && idx <= mid) { update_point(2 * node, start, mid, idx, val); } else { update_point(2 * node + 1, mid + 1, end, idx, val); } tree[node] = merge(tree[2 * node], tree[2 * node + 1]); } } // Thao tác 2: Cập nhật đoạn (Range Update - Division) void update_range_div(int node, int start, int end, int l, int r) { // Nếu đoạn hiện tại nằm ngoài phạm vi cần update hoặc max_val = 0 (chia cũng bằng 0) if (start > end || start > r || end < l || tree[node].max_val == 0) { return; } // Nếu là nút lá, thực hiện chia if (start == end) { tree[node].sum /= K; tree[node].max_val /= K; return; } // Nếu không phải lá, đi xuống con int mid = (start + end) / 2; update_range_div(2 * node, start, mid, l, r); update_range_div(2 * node + 1, mid + 1, end, l, r); // Cập nhật lại nút cha sau khi con thay đổi tree[node] = merge(tree[2 * node], tree[2 * node + 1]); } // Thao tác 3: Truy vấn tổng (Range Sum Query) ll query(int node, int start, int end, int l, int r) { if (start > end || start > r || end < l) { return 0; } if (l <= start && end <= r) { return tree[node].sum; } int mid = (start + end) / 2; ll p1 = query(2 * node, start, mid, l, r); ll p2 = query(2 * node + 1, mid + 1, end, l, r); return p1 + p2; } int main() { // Tối ưu nhập xuất ios_base::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> N >> Q >> K)) return 0; for (int i = 1; i <= N; i++) { cin >> arr[i]; } build(1, 1, N); for (int i = 0; i < Q; i++) { int type; cin >> type; if (type == 1) { int idx; ll val; cin >> idx >> val; update_point(1, 1, N, idx, val); } else if (type == 2) { int l, r; cin >> l >> r; // Nếu K = 1, phép chia không thay đổi gì, bỏ qua để tiết kiệm thời gian if (K > 1) { update_range_div(1, 1, N, l, r); } } else if (type == 3) { int l, r; cin >> l >> r; cout << query(1, 1, N, l, r) << "\n"; } } return 0; }