题解 CF438D 【The Child and Sequence】
Juan_feng
2018-11-26 20:04:19
## 分块也可以通过此题qwq
~~跑的贼慢= =~~
咳咳，进入正题。
区间求和和单点修改都是基操，这里就不深入讲解了
看看区间取%
方法之前的dalao都说了，维护每一个块内的最大值，如果这个最大值小于膜数就直接跳过此块，散块暴力修改，因为每次修改至少让一个数减小一半，所以每个数最多修改次数为log级别的。 **然而分块怎么维护最大值呢= =？** 愚蠢如我自然只能用蠢办法了QAQ ：
用vector保存每个块内的数值大小， 修改的时候只要erase掉当前数值再insert修改后的数值就好了。 取最大值的时候就直接取出vector的最后一个值。
大概就是这样啊qaq
**感觉还有优化的空间**，小蒟蒻的题解权当抛砖引玉了qwqwq
如果还有什么问题或者意见建议的话不妨直接私信小蒟蒻qaq
**那么代码如下**
```
#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; // 功德圆满
}
```