CF438D The Child and Sequence [線段樹+均攤分析]

​​傳送門​​

如果一個數取模了有變換, 那麼它至少縮小一半, 是以最多 log 次就變成1了

#include<bits/stdc++.h>
#define N 200050
using namespace std;
typedef long long ll;
int read(){ int x; scanf("%d", &x); return x;}
ll Max[N<<2], Sum[N<<2]; int n, m, a[N];
void Pushup(int x){
  Max[x] = max(Max[x<<1], Max[x<<1|1]);
  Sum[x] = Sum[x<<1] + Sum[x<<1|1];
}
void Build(int x, int l, int r){
  if(l == r){ Max[x] = Sum[x] = a[l]; return;}
  int mid = (l+r) >> 1; Build(x<<1, l, mid); Build(x<<1|1, mid+1, r);
  Pushup(x);
}
void Modify(int x, int l, int r, int pos, int val){
  if(l == r){ Max[x] = Sum[x] = val; return;}
  int mid = (l+r) >> 1; 
  if(pos <= mid) Modify(x<<1, l, mid, pos, val);
  else Modify(x<<1|1, mid+1, r, pos, val);
  Pushup(x);
}
void PushMod(int x, int l, int r, int mod){
  if(Max[x] < mod) return; 
  if(l == r){ Max[x] %= mod; Sum[x] %= mod; return;}
  int mid = (l+r) >> 1;
  PushMod(x<<1, l, mid, mod); PushMod(x<<1|1, mid+1, r, mod);
  Pushup(x);
}
void Mod(int x, int l, int r, int L, int R, int mod){
  if(L<=l && r<=R){ PushMod(x, l, r, mod); return;} 
  int mid = (l+r) >> 1;
  if(L<=mid) Mod(x<<1, l, mid, L, R, mod);
  if(R>mid) Mod(x<<1|1, mid+1, r, L, R, mod);
  Pushup(x);
}
ll Quary(int x, int l, int r, int L, int R){
  if(L<=l && r<=R) return Sum[x]; int mid = (l+r) >> 1; ll ans = 0;
  if(L<=mid) ans += Quary(x<<1, l, mid, L, R);
  if(R>mid) ans += Quary(x<<1|1, mid+1, r, L, R);
  return ans;
}
int main(){
  n = read(), m = read(); for(int i=1; i<=n; i++) a[i] = read(); Build(1, 1, n);
  while(m--){ int op = read();
    if(op == 1){ int l = read(), r = read(); printf("%lld\n", Quary(1, 1, n, l, r));}
    if(op == 2){ int l = read(), r = read(), x = read(); Mod(1, 1, n, l, r, x);}
    if(op == 3){ int k = read(), x = read(); Modify(1, 1, n, k, x);}
  } return 0;
}