一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 CF438D 【The Child and Sequence】

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

分块也可以通过此题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; // 功德圆满
}