Kaaleppi's run

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define N (1<<18)

using namespace std;

ll v[2 * N];
ll w[2 * N];

void setv (int k, ll n) {
  k += N;
  w[k] = v[k] = n;
  for (k /= 2; k >= 1; k /= 2) {
    v[k] = v[2 * k] + v[2 * k + 1];
    w[k] = max(w[2 * k], w[2 * k + 1]);
  }
}

ll sum (int a, int b) {
  a += N;
  b += N;
  ll s = 0;
  while (a <= b) {
    if (a % 2) s += v[a++];
    if (b % 2 == 0) s += v[b--];
    a /= 2; b /= 2;
  }
  return s;
}

void rage (int a, int b, int i, int l, int r, ll m) {
  if (b < l || a > r) return;
  //cout<<"QUERY1 "<<a<<" "<<b<<" "<<i<<" "<<w[i]<<endl;
  if (w[i] < m) return;
  //cout<<"QUERY2 "<<a<<" "<<b<<endl;
  if (a == b) {
    //cout<<"SET "<<a<<" to "<<v[a + N]<<" % "<<m<<endl;
    setv(a, v[a + N] % m);
    return;
  }
  int q = r - l + 1;
  q /= 2;
  rage(a, min(r - q, b), 2 * i, l, r - q, m);
  rage(max(a, l + q), b, 2 * i + 1, l + q, r, m);
}

int main () {
  int n, q;
  cin>>n>>q;
  for (int i = 0; i < n; i++) {
    ll x;
    cin>>x;
    setv(i, x);
  }
  for (int i = 0; i < q; i++) {
    int t;
    cin>>t;
    if (t == 1) {
      ll a, b, c;
      cin>>a>>b>>c;
      rage(a - 1, b - 1, 1, 0, N - 1, c);
    } else {
      ll a, b;
      cin>>a>>b;
      cout<<sum(a - 1, b - 1)<<endl;
    }
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED