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