今天咕咕咕吧。

分块

定义

• 区间：数列中连续一段的元素是区间。
• 区间操作：某个区间$[a,b]$的所有元素进行某种改动的操作是区间操作。
• 块：数列划分成的若干个不相交的区间是块。
• 整块：在进行一个区间操作时，完整包含于区间的块是整块。
• 不完整的块：在进行一个区间操作时，只有部分包含于区间的块是不完整的块。

思想

将连续$x$个元素分为一个块。

对于每一个操作$[L,R]$，一定是中间包含了若干（或者没有）完整块，两边剩余不超过$2x$个位置，即$[l,k \times x],[k \times x + 1,(k+1)\times x] \cdots [k_n \times z+1,r]$这种形式。

对于完整块可以统一处理，如果可以做到$O(1)￥每一个块，则时间复杂度为$O(\fracnx)$。

对于剩余的$2x$个点，可以暴力处理$O(x)$。

理论上，当$x=\sqrt{n}$时，每次操作的时间复杂度降到最低$O(\sqrt{n})$

若上面两种情况的任意一种需要多一个$log_2$的复杂度，那么可以通过调整块的大小来使得每次操作的复杂度变为$O(\sqrt{nlog_2n})$

代码

#include <iostream>
#include <cmath>
using namespace std;
template < class T >
struct BioArray {
    int blo, n;
    int bl[100005];
//    vector< int > bl;
    T val[100005],tag[100005],sum[100005];
//    vector< T > val, tag, sum;
    void refresh( int nb, int b = 0 ) {
        n = nb;
//        bl.clear();
//        bl.push_back( 0 );
//        val.clear();
//        val.push_back( 0 );
//        tag.clear();
//        tag.push_back( 0 );
//        sum.clear();
//        sum.push_back( 0 );
        if ( !b ) {
            b = sqrt( n );
        }
        blo = b;
        for ( int i = 1; i <= n; i++ ) {
            bl[i]=( i - 1 ) / blo + 1;
//            bl.push_back( ( i - 1 ) / blo + 1 );
//            val.push_back( 0 );
//            tag.push_back( 0 );
        }
    }
    void updata( int a, int b, T c ) {
        for ( int i = a; i <= min( bl[a] * blo, b ); i++ )
            val[i] += c, sum[bl[a]] += c;
        if ( bl[a] != bl[b] )
            for ( int i = ( bl[b] - 1 ) * blo + 1; i <= b; i++ )
                val[i] += c, sum[bl[b]] += c;
        for ( int i = bl[a] + 1; i <= bl[b] - 1; i++ )
            tag[i] += c;
    }
    void updata( int a, T c ) {
        val[a] += c, sum[bl[a]] += c;
    }
    T query( int a, int b ) {
        T ans = 0;
        for ( int i = a; i <= min( bl[a] * blo, b ); i++ ) {
            ans += tag[bl[a]] + val[i];
        }
        if ( bl[a] != bl[b] ) {
            for ( int i = ( bl[b] - 1 ) * blo + 1; i <= b; i++ ) {
                ans += tag[bl[b]] + val[i];
            }
        }
        for ( int i = bl[a] + 1; i <= bl[b] - 1; i++ ) {
            ans += tag[i] * blo + sum[i];
        }
        return ans;
    }
    T query( int a ) {
        return val[a] + tag[bl[a]];
    }
};
int main() {
    ios::sync_with_stdio( false );
    int n, m;
    BioArray< long long > a;
    cin >> n >> m;
    a.refresh( n );
    for ( int i = 1; i <= n; i++ ) {
        long long t;
        cin >> t;
        a.updata( i, t );
    }
    for ( int i = 1; i <= m; i++ ) {
        char opt;
        long long l, r, c;
        cin >> opt >> l >> r;
        switch ( opt ) {
            case 'C':
                cin >> c;
                a.updata( l, r, c );
                break;
            case 'Q':
                cout << a.query( l, r ) << endl;
                break;
            default:
                cerr << "ERROR" << endl;
        }
    }
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/452.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。