# 一无所|知的小|J f

### 题解 CF438D 【The Child and Sequence】

posted on 2018-11-26 20:04:19 | under 题解 |

## 分块也可以通过此题qwq

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define maxn 100010
#define ll long long
#define re register
#define FOR(i, l, r) for(re ll i = l; i <= r; ++i)
using namespace std;

ll n, m, c, r, t, x, y, z, k; //小蒟蒻太懒就全开上long long了
ll sq;
ll a[maxn], b[maxn], maxx[maxn], ans[maxn];
vector<ll> ve[1001];

inline void in(re ll &x){ //快读
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x=x*f;
}

void out(re ll a){
if(a<0){
a*=-1;
putchar('-');
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}

ll query(ll x, ll y) { //求和
ll anss = 0;
FOR(i, x, min(y, b[x]*sq))
anss += a[i];
if(b[x] != b[y])
FOR(i, (b[y]-1)*sq+1, y)
anss += a[i];
FOR(i, b[x]+1, b[y]-1)
anss += ans[i];
return anss;
}

void change(ll x, ll y, ll p) { //区间取%
FOR(i, x, min(y, b[x]*sq)) { //散块暴力修改
if(a[i] >= p) {
ans[b[x]] -= a[i];
ve[b[x]].erase(lower_bound(ve[b[x]].begin(), ve[b[x]].end(), a[i]));
a[i] %= p;
ans[b[x]] += a[i];
ve[b[x]].insert(lower_bound(ve[b[x]].begin(), ve[b[x]].end(), a[i]), a[i]);
}
}
if(b[x] != b[y])
FOR(i, (b[y]-1)*sq+1, y) {
if(a[i] >= p) {
ans[b[y]] -= a[i];
ve[b[y]].erase(lower_bound(ve[b[y]].begin(), ve[b[y]].end(), a[i]));
a[i] %= p;
ans[b[y]] += a[i];
ve[b[y]].insert(lower_bound(ve[b[y]].begin(), ve[b[y]].end(), a[i]), a[i]);
}
}
FOR(i, b[x]+1, b[y]-1) { //整块判断是否需要修改，是则暴力去找
ll nc = ve[i].size();
if(ve[i][nc-1] >= p)
FOR(j, (i-1)*sq+1, i*sq) {
if(a[j] >= p) {
ans[i] -= a[j];
ve[i].erase(lower_bound(ve[i].begin(), ve[i].end(), a[j]));
a[j] %= p;
ans[i] += a[j];
ve[i].insert(lower_bound(ve[i].begin(), ve[i].end(), a[j]), a[j]);
}
}
}
}

int main() {
in(n), in(m);
sq = sqrt(n);
FOR(i, 1, n) { //预处理
in(a[i]), b[i] = (i-1)/sq+1, ans[b[i]] += a[i];
ve[b[i]].insert(lower_bound(ve[b[i]].begin(), ve[b[i]].end(), a[i]), a[i]);
}
FOR(i, 1, m) {
in(t);
if(t == 1) {
in(x), in(y);
out(query(x, y));
putchar(10);
}
if(t == 2) {
in(x), in(y), in(z);
change(x, y, z);
}
if(t == 3) {
in(x), in(k);
ans[b[x]] -= a[x];
ve[b[x]].erase(lower_bound(ve[b[x]].begin(), ve[b[x]].end(), a[x]));
a[x] = k;
ans[b[x]] += k;
ve[b[x]].insert(lower_bound(ve[b[x]].begin(), ve[b[x]].end(), a[x]), a[x]);
}
}
return 0; // 功德圆满
}