【算法】分块——教主的魔法&不勤劳的图书管理员

由不勤劳的图书管理员带入了分块的坑，深深地被其暴力与优雅所征服。分块的实质就是将暴力块状封装起来，一整块的部分就一整块处理，零碎的部分就怎么暴力怎么来。因为分块大小的原因，限制了零碎部分数据的数量级，所以复杂度得以保证。

1.教主的魔法：可以算得上是一个分块的板子题。对于每一个块内sort排序，保存id值。对于修改，块内的找到点暴力修改之后重新排序，一整个块的不改变相对大小关系，所以直接外部记录累加的值。查询也一样，块外暴力，块内二分查找。

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define maxn 2000000

#define maxb 1050

int n, q, B, sum[maxb], a[maxn], cnt[maxb];

struct node

{

    int v, id;

}c[maxb][maxb];

int read()

{

    int x = ;

    char c;

    c = getchar();

    while(c < '' || c > '') c = getchar();

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x;

}

bool cmp(node a, node b)

{

    return a. v < b.v;

}

void Vio_C(int b, int x, int w)

{

    c[b][x].v += w;

}

void Change(int L, int R, int W)

{

    int a = L / B, b = R / B;

    if(a == b)

    {

        for(int i = ; i <= cnt[a]; i ++)

            if(c[a][i].id >= L && c[a][i].id <= R) Vio_C(a, i, W);

            sort(c[a] + , c[a] + cnt[a] + , cmp);
　　　　　return 0;

    }

    for(int i = ; i <= cnt[a]; i ++)

        if(c[a][i].id >= L) Vio_C(a, i, W);

    sort(c[a] + , c[a] + cnt[a] + , cmp);

    for(int i = ; i <= cnt[b]; i ++)

        if(c[b][i].id <= R) Vio_C(b, i, W);

    sort(c[b] + , c[b] + cnt[b] + , cmp);

    for(int i = a + ; i < b; i ++)

        sum[i] += W;

}

int check(int b, int C)

{

    C -= sum[b];

    int ans = cnt[b] + , l = , r = cnt[b];

    while(l <= r)

    {

        int mid = (l + r) >> ;

        if(c[b][mid].v >= C) ans = mid, r = mid - ;

        else l = mid + ;

    }

    return cnt[b] - ans + ;

}

void Query(int L, int R, int C)

{

    int a = L / B, b = R / B;

    int ans = ;

    if(a == b)

    {

        C -= sum[a];

        for(int i = ; i <= cnt[a]; i ++)

            if(c[a][i].id >= L && c[a][i].id <= R && c[a][i].v >= C) ans ++;

        printf("%lld\n", ans);

        return;

    }

    for(int i = ; i <= cnt[a]; i ++)

           if(c[a][i].id >= L && c[a][i].v + sum[a] >= C) ans ++;

    for(int i = ; i <= cnt[b]; i ++)

        if(c[b][i].id <= R && c[b][i].v + sum[b] >= C) ans ++;

    for(int i = a + ; i < b; i ++)

        ans += check(i, C);

    printf("%lld\n", ans);

    return;

}

signed main()

{

    n = read(), q = read();

    B = sqrt(n);

    for(int i = ; i <= n; i ++)

    {

        a[i] = read(); int block = i / B;

        c[block][++ cnt[block]].v = a[i];

        c[block][cnt[block]].id = i;

        if(((i / B) != (i + ) / B) || i == n)

            sort(c[block] + , c[block] + cnt[block] + , cmp);

    }

    for(int i = ; i <= q; i ++)

    {

        char c; cin >> c;

        int L = read(), R = read(), W = read();

        if(c == 'M') Change(L, R, W);

        else Query(L, R, W);

    }

    return ;

}

2.不勤劳的图书管理员

这题首先注意到交换a,b的位置，只会影响到a,b之间的数。在一段区间里，a对杂乱值的贡献是多少？不难发现=在a之前且应当在a之后的书本杂乱值之和+v[a]*前面书本的个数。所以我们对每一个块使用两个树状数组，一个纪录个数，一个记录页数的前缀和，块内的利用树状数组快速查询，块外的暴力枚举计算即可。

因为此题代码是Kuai的（那个时候还不会写分块），所以就不贴代码啦。

【算法】分块——教主的魔法&不勤劳的图书管理员的相关教程结束。