成都外国语学校信息学八月集训 Day3

今天咕咕咕吧。

00:00
加载中……请稍等……

分块

定义

  • 区间:数列中连续一段的元素是区间。
  • 区间操作:某个区间$[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;
}
Last modification:August 21st, 2019 at 09:30 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment