fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 1e5+5;
  7.  
  8. int n, m, a[N];
  9. int mx[4*N];
  10. ll st[4*N];
  11.  
  12. void pull(int id) {
  13.     mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  14.     st[id] = st[id << 1] + st[id << 1 | 1];
  15. }
  16.  
  17. void build(int id, int l, int r) {
  18.     if (l == r) {
  19.         st[id] = mx[id] = a[l];
  20.         return;
  21.     }
  22.     int mid = (l + r) >> 1;
  23.     build(id << 1, l, mid);
  24.     build(id << 1 | 1, mid + 1, r);
  25.     pull(id);
  26. }
  27.  
  28. void update(int id, int l, int r, int k, int x) {
  29.     if (l == r) {
  30.         st[id] = mx[id] = x;
  31.         return;
  32.     }
  33.     int mid = (l + r) >> 1;
  34.     if (k <= mid) update(id << 1, l, mid, k, x);
  35.     else update(id << 1 | 1, mid + 1, r, k, x);
  36.     pull(id);
  37. }
  38.  
  39. void update_mod(int id, int l, int r, int u, int v, int x) {
  40.     if (v < l || r < u || mx[id] < x) return;
  41.     if (l == r) {
  42.         st[id] %= x;
  43.         mx[id] %= x;
  44.         return;
  45.     }
  46.     int mid = (l + r) >> 1;
  47.     update_mod(id << 1, l, mid, u, v, x);
  48.     update_mod(id << 1 | 1, mid + 1, r, u, v, x);
  49.     pull(id);
  50. }
  51.  
  52. ll query(int id, int l, int r, int u, int v) {
  53.     if (v < l || r < u) return 0;
  54.     if (u <= l && r <= v) return st[id];
  55.     int mid = (l + r) >> 1;
  56.     return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
  57. }
  58.  
  59. void solve() {
  60.     cin >> n >> m;
  61.     for (int i = 1; i <= n; i++) cin >> a[i];
  62.     build(1, 1, n);
  63.     while (m--) {
  64.         int op; cin >> op;
  65.         if (op == 1) {
  66.             int l, r; cin >> l >> r;
  67.             cout << query(1, 1, n, l, r) << '\n';
  68.         } else if (op == 2) {
  69.             int l, r, x; cin >> l >> r >> x;
  70.             update_mod(1, 1, n, l, r, x);
  71.         } else if (op == 3) {
  72.             int k, x; cin >> k >> x;
  73.             update(1, 1, n, k, x);
  74.         }
  75.     }
  76. }
  77.  
  78. int main() {
  79.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  80.  
  81.     int tests = 1; // cin >> tests;
  82.     while (tests--) solve();
  83.  
  84.     #ifdef LOCAL
  85.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  86.     #endif
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5596KB
comments (?)
stdin
copy 
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10
stdout
copy 
49
15
23
1
9
https://ideone.com/sccWpi
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!