P1438 无聊的数列

问题

P1438 无聊的数列
维护一个数列，支持在区间上依次加上首项为 $K$、公差为 $D$ 的等差数列，以及查询单点当前值。

数据规模：$n,m\le 10^5$。

如果直接考虑，对原序列区间加上这个等差数列，实现起来复杂度非常高。

注意到最后只需要查询单点当前值，这其实就暗示我们在差分后的数组上操作，最后求前缀值，得到原数组的当前值。

那么核心转化就是在差分数组上修改，也就是在 $l$ 处加 $K$，在 $[l + 1, r]$ 上加 $D$，再在 $r + 1$ 处减 $K + (r - l)D$。

最后用线段树维护区间加和区间和即可；这组操作也能用树状数组完成，但当前写法沿用了正在练习的懒标记结构。

▶

P1438-Seg

#define ls ( u << 1 )
#define rs ( u << 1 | 1 )

struct SegTree {
/* ================================================== */
struct Node { 
    int l, r; 
    ll sum;
    ll add; 
} tr[maxn << 2];

int len( int u ) { 
    return tr[u].r - tr[u].l + 1; 
}

void push_up( int u ) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

void apply( int u, ll val ) {
    tr[u].sum += val * len( u );
    tr[u].add += val;
}

void push_down( int u ) {
    if( !tr[u].add ) return ;
    apply( ls, tr[u].add );
    apply( rs, tr[u].add );
    tr[u].add = 0;
}

void build( int u, int l, int r, ll *val ) {
    tr[u] = { l, r, 0, 0 };
    if( l == r ) {
        tr[u].sum = val[l];
        return ;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid, val );
    build( rs, mid + 1, r, val );
    push_up( u );
}

void upd( int u, int l, int r, ll val ) {
    if( l <= tr[u].l && tr[u].r <= r ) {
        apply( u, val );
        return ;
    }
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r, val );
    if( mid < r ) upd( rs, l, r, val );
    push_up( u );
}

ll ask( int u, int l, int r ) {
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].sum;
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    ll res = 0;
    if( l <= mid ) res += ask( ls, l, r );
    if( mid < r ) res += ask( rs, l, r );
    return res;
}
/* ================================================== */
} seg;

ll a[maxn], d[maxn];

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );
    for( int i = 1; i <= n; ++ i ) d[i] = a[i] - a[i-1];

    seg.build( 1, 1, n, d );
    for( int i = 1; i <= m; ++ i ) {
        int opt = read( );
        if( opt == 1 ) {
            int l = read( ), r = read( );
            ll K = read( ), D = read( );
            ll val = K + (r - l) * D;
            seg.upd( 1, l, l, K );
            if( l + 1 <= r ) seg.upd( 1, l + 1, r, D );
            if( r + 1 <= n ) seg.upd( 1, r + 1, r + 1, -val );
        }
        else {
            int p = read( );
            cout << seg.ask( 1, 1, p ) << '\n';
        }
    }
}

▶

P1438-Bit

struct BIT {
/* ================================================== */
ll tr1[maxn], tr2[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr1, tr1 + sz + 2, 0 );
    fill( tr2, tr2 + sz + 2, 0 );
}
void build( int N, ll val[] ) {
    init( N );
    for( int i = 1; i <= N; ++ i ) add( i, i, val[i] );
}
void add_point( int idx, ll val ) {
    for( int i = idx; i <= sz; i += i & -i ) {
        tr1[i] += val, tr2[i] += idx * val;
    }
} // 差分数组 d[idx] += val
void add( int l, int r, ll val ) {
    add_point( l, val );
    if( r + 1 <= sz ) add_point( r + 1, -val );
} // 区间 [l, r] 加 val
ll ask_tree( ll tr[], int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) res += tr[i];
    return res;
}
ll ask( int idx ) {
    return ( idx + 1LL ) * ask_tree( tr1, idx ) - ask_tree( tr2, idx );
} // 查询原数组前缀和 [1, idx]
ll ask( int l, int r ) {
    return ask( r ) - ask( l - 1 );
} // 查询原数组区间和 [l, r]
/* ================================================== */
} bit;

ll a[maxn], d[maxn];

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );
    for( int i = 1; i <= n; ++ i ) d[i] = a[i] - a[i-1];
    
    bit.build( n, d );
    for( int i = 1; i <= m; ++ i ) {
        int opt = read( );
        if( opt == 1 ) {
            int l = read( ), r = read( );
            ll K = read( ), D = read( );
            bit.add( l, l, K );
            if( l + 1 <= r ) bit.add( l + 1, r, D );
            ll val = K + (r - l) * D;
            if( r + 1 <= n ) bit.add( r + 1, r + 1, -val );
        }
        else {
            int p = read( );
            cout << bit.ask( p ) << '\n';
        }
    }
}

记录

• 归属：方法/差分、方法/表示变换、数据结构/树状数组。
• 新增：等差区间修改在差分表示中只留下常量区间和两个边界变化。
• 分类：保留；核心增量是把等差修改转成差分数组上的常量区间修改。