Rt， 数列分块入门1，提交记录

代码

// Problem: #6277. 数列分块入门 1
// Contest: LibreOJ
// URL: https://loj.ac/p/6277
// Memory Limit: 256 MB
// Time Limit: 100 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
long long int data[ 1000 ], tag[ 1000 ];
int st[ 1000 ], ed[ 1000 ], belong[ 500010 ], size[ 1000 ];
int num;
int a[ 500010 ];
void init( int n )
{
    num = sqrt( n );
    for ( int i = 1; i <= num; i++ )
    {
        st[ i ] = n / num * ( i - 1 ) + 1;
        ed[ i ] = n / num * i;
    }
    ed[ num ] = n;
    for ( int i = 1; i <= num; i++ )
    {
        for ( int j = st[ i ]; j <= ed[ i ]; j++ )
        {
            belong[ j ] = i;
            data[ i ] += a[ j ];
        }
        size[ i ] = ed[ i ] - st[ i ] + 1;
    }
}
void pushdown( int x )
{
    for ( int i = st[ x ]; i <= ed[ x ]; i++ )
    {
        a[ i ] += tag[ x ];
    }
    tag[ x ] = 0;
}
int query( int l, int r )
{
    int ans = 0;
    int b = belong[ l ];
    if ( l != st[ belong[ l ] ] )
    {
        pushdown( belong[ l ] );
        for ( int i = l; i <= min( ed[ belong[ l ] ], r ); i++ )
        {
            ans += a[ i ];
            // cerr<<i<<endl;
        }
        b++;
    }
    // cerr<<ans<<endl;
    int e = belong[ r ];
    if ( r != ed[ belong[ r ] ] )
    {
        pushdown( belong[ r ] );
        for ( int i = max( st[ belong[ r ] ], l ); i <= r; i++ )
        {
            ans += a[ i ];
            // cerr<<i<<endl;
        }
        e--;
    }
    // cerr<<ans<<endl;
    for ( int i = b; i <= e; i++ )
    {
        ans += data[ i ];
    }
    return ans;
}
void add( int l, int r, int x )
{
    int b = belong[ l ];
    if ( l != st[ belong[ l ] ] )
    {
        for ( int i = l; i <= min( ed[ belong[ l ] ], r ); i++ )
        {
            a[ i ] += x;
            data[ b ] += x;
            // cerr<<i<<endl;
        }
        b++;
    }
    // cerr<<ans<<endl;
    int e = belong[ r ];
    if ( r != ed[ belong[ r ] ] )
    {
        for ( int i = max( st[ belong[ r ] ], l ); i <= r; i++ )
        {
            a[ i ] += x;
            data[ e ] += x;
            // cerr<<i<<endl;
        }
        e--;
    }
    // cerr<<ans<<endl;
    for ( int i = b; i <= e; i++ )
    {
        data[ i ] += size[ i ] * x;
        tag[ i ] += x;
    }
}
inline int read()
{
    char c = getchar();
    int x = 0, f = 1;
    while ( c < '0' || c > '9' )
    {
        if ( c == '-' )
            f = -1;
        c = getchar();
    }
    while ( c >= '0' && c <= '9' )
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int main()
{
    int n;
    cin >> n;
    for ( int i = 1; i <= n; i++ )
    {
        a[ i ] = read();
    }
    init( n );
    while ( n-- )
    {
        int opt = read(), x = read(), y = read(), k = read();
        if ( opt == 0 )
        {
            add( x, y, k );
        }
        else
        {
            pushdown( belong[ y ] );
            printf( "%d\n", a[ y ] );
        }
        /*for (int i=1;i<=num;i++)
            cerr<<data[i]<<" ";
        cerr<<endl;
        for (int i=1;i<=num;i++)
            cerr<<tag[i]<<" ";
        cerr<<endl;
        for (int i=1;i<=n;i++)
            cerr<<a[i]<<" ";
        cerr<<endl;*/
    }
}

但这份代码过了洛谷的树状数组2