P3130 题解

· · 题解

索引：分块是一种优美的暴力。

分块为什么优美

简述分块思想：将原序列划分成一堆块，大块整体操作，小块暴力更改。

分块的优美之处：我们尝试将原序列划分成 t 个元素一块的若干堆块，不管是查询还是修改操作，如果我们暴力更改小块，复杂度是 \mathcal{O}(t)，如果加上大块的整体操作，复杂度是 \mathcal{O}(\frac{n}{t}+t)，根据均值不等式，当 t=\sqrt{n} 时最优，复杂度均为 \mathcal{O}(\sqrt{n})。

整体复杂度分析：我们不妨令 n、q 同阶，则整体复杂度为 \mathcal{O}(n\sqrt{n})，虽然在渐进意义上不如线段树的 \log，但是对于本题一样的数据仍然绰绰有余（虽然带点小常数）。

为什么要用分块：好想，实现简单（总比懒标记好记），直观。

题目实现

首先最为朴素的区间加和求和操作，我们对于小块直接暴力更改、求和，对于大块，考虑维护一个增量标记 add，表示这个块加了多少而我们还没有统计。最后加上增量标记乘区间长度即可。

对于稍微不朴素的区间最小值操作，显然如果我们对整块进行区间加，那么这个块的最小值也相应地增加这个数，所以可以在 \mathcal{O}(1) 时间内完成。但是如果对一个块的一部分进行操作（也就是小块），那整个大块的最小值不一定会变成什么样子，所以我们选择暴力重更新。\mathcal{O}(\sqrt{n}) 仍然可以接受。

千万别忘了 add。

其余的看代码：

#include <bits/stdc++.h>
#define inf LONG_LONG_MAX 
#define f(i ,m ,n ,x) for (int i = (m) ;i <= (n) ;i += (x))
using namespace std ;
template < typename T > inline void read ( T&x ) {
    x = 0 ;
    bool flag (0) ;
    register char ch = getchar () ;
    while (! isdigit (ch)) {
        flag = ch == '-' ;
        ch = getchar () ;
    }
    while (isdigit (ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48) ;
        ch = getchar () ;
    }
    flag ? x = -x : 0 ;
}
const int N = 2e5 + 7 ;
const int M (666) ;
#define int long long
int n ,q ,l[M] ,r[M] ,belong[N] ;
int a[N] ,sum[M] ,add[M] ,minn[M] ;
namespace shin {
    inline void modify (int L ,int R ,int k) {
        int p = belong[L] ,q = belong[R] ;
        if (p == q) {
            minn[p] = inf ; // 直接重新更新
            f (i ,l[p] ,r[p] ,1) { // L、R 在一个块内
                if (i >= L && i <= R) {
                    a[i] += k ; // 区间加
                }
                minn[p] = min (minn[p] ,a[i] + add[p]) ;
            }
            sum[p] += (R - L + 1) * k ;
            return ;
        }
    // 若不在，则可以变成若干大块加两小块的样式
        minn[p] = minn[q] = inf ;
        f (i ,l[p] ,r[p] ,1) {
            if (i >= L) {
                a[i] += k ;
            } 
            minn[p] = min (minn[p] ,a[i] + add[p]) ;
        }
        sum[p] += (r[p] - L + 1) * k ;
        f (i ,l[q] ,r[q] ,1) {
            if (i <= R) {
                a[i] += k ;
            }
            minn[q] = min (minn[q] ,a[i] + add[q]) ;
        }
        sum[q] += (R - l[q] + 1) * k ;
        f (i ,p + 1 ,q - 1 ,1) {
            add[i] += k ;
            minn[i] += k ;
        }
    }
    inline int find (int L ,int R) {
        int p = belong[L] ,q = belong[R] ;
        if (p == q) {
            int ans = inf ;
            f (i ,L ,R ,1) {
                ans = min (ans ,a[i] + add[p]) ;
            } 
            return ans ;
        }
        int ans = inf ;
        f (i ,L ,r[p] ,1) {
            ans = min (ans ,a[i] + add[p]) ;
        }
        f (i ,l[q] ,R ,1) {
            ans = min (ans ,a[i] + add[q]) ;
        }
        f (i ,p + 1 ,q - 1 ,1) {
            ans = min (ans ,minn[i]) ;
        }
        return ans ;
    }
    inline int query (int L ,int R) {
        int p = belong[L] ,q = belong[R] ;
        if (p == q) {
            int ans (0) ;
            f (i ,L ,R ,1) {
                ans += a[i] + add[p] ;
            }
            return ans ;
        } 
        int ans (0) ;
        f (i ,L ,r[p] ,1) {
            ans += a[i] + add[p] ;
        }
        f (i ,l[q] ,R ,1) {
            ans += a[i] + add[q] ;
        }
        f (i ,p + 1 ,q - 1 ,1) {
            ans += sum[i] + add[i] * (r[i] - l[i] + 1) ;
        }
        return ans ;
    }
}
signed main () {
    read (n) ,read (q) ;
    f (i ,1 ,n ,1) {
        read (a[i]) ; 
    }
    int t = sqrt (n) ; // 求块长和块数
    f (i ,1 ,t ,1) {
        minn[i] = inf ;
        l[i] = (i - 1) * t + 1 ;
        r[i] = i * t ;
    } // 记录大块左右断点
    if (r[t] < n) {
        t ++ ;
        l[t] = r[t - 1] + 1 ;
        r[t] = n ;
    } // t 很可能不是真正的 sqrt (n)，也就是说最后可能会剩下一个小块
    f (i ,1 ,t ,1) {
        f (j ,l[i] ,r[i] ,1) {
            belong[j] = i ;
            sum[i] += a[j] ;
            minn[i] = min (minn[i] ,a[j]) ;
        }
    } // 记录每个点属于哪个块，顺带统计块和和块内最小值
    do {
        int a ,b ;
        int c ;
        char ch ;
        cin >> ch ;
        if (ch == 'P') {
            read (a) ,read (b) ,read (c) ;
            shin :: modify (a ,b ,c) ;
        }
        else if (ch == 'M') {
            read (a) ,read (b) ;
            cout << shin :: find (a ,b) << '\n' ; 
        }
        else {
            read (a) ,read (b) ;
            cout << shin :: query (a ,b) << '\n' ;
        }
    } while (q -- != 1) ;
    return 0 ;
}