CFR 444 C. DZY Loves Colors ( Segment Tree, Dummy Constraints )
題意:
給長度 N 的數列 A[]。初始時 A[ i ] = i, for all 1 ≤ i ≤ N。
M 筆詢問,兩種形式:
1 l r x:將 [ l, r ] 都塗色為 x
2 l r:輸出 [ l, r ] 的貢獻總和
初始時所有元素的貢獻為 0。
當一個元素由 u 變為 v 時,增加貢獻 abs( u - v )。
制約:
1 ≤ N, M ≤ 1e5
1 ≤ X ≤ 1e8
解法:
首先注意到,顏色有連續性。
如果將同一個顏色的區間統一管理,那麼一共最多只要塗 O( N + M ) 量級的區間,因為每多合併一個,就會少一個合併的機會。
因此可以用線段樹管理區間是否顏色一致,更新的時候總是向下拜訪到顏色一致的區間。
複雜度:
O( N lg N + M )
#include <bits/stdc++.h> using namespace std; const int MAXN = 1 << 17; int N, M; int col[ MAXN << 1 ]; long long tag[ MAXN << 1 ]; long long score[ MAXN << 1 ]; void push( int t, int lb, int rb ) { for( int r = 0; r < 2; ++r ) { if( col[ t ] ) col[ t << 1 | r ] = col[ t ]; score[ t << 1 | r ] += 1LL * ( rb - lb + r >> 1 ) * tag[ t ]; tag[ t << 1 | r ] += tag[ t ]; } tag[ t ] = 0; } void pull( int t ) { col[ t ] = ( col[ t << 1 ] == col[ t << 1 | 1 ] ) * col[ t << 1 ]; score[ t ] = score[ t << 1 ] + score[ t << 1 | 1 ]; } signed main() { ios::sync_with_stdio( 0 ); cin >> N >> M; static function< void( int, int, int ) > build = [ & ]( int t, int lb, int rb ) { if( lb + 1 == rb ) return col[ t ] = lb + 1, void(); build( t << 1, lb, lb + rb >> 1 ); build( t << 1 | 1, lb + rb >> 1, rb ); }; build( 1, 0, N ); for( int mi = 0; mi < M; ++mi ) { int op, ql, qr; cin >> op >> ql >> qr; --ql; if( op == 1 ) { int x; cin >> x; static function< void( int, int, int, int, int, int ) > update = [ & ]( int t, int lb, int rb, int ql, int qr, int x ) { static function< void( int, int, int, int ) > set = [ & ]( int t, int lb, int rb, int x ) { if( col[ t ] ) { score[ t ] += 1LL * ( rb - lb ) * abs( x - col[ t ] ); tag[ t ] += abs( x - col[ t ] ); col[ t ] = x; return; } push( t, lb, rb ); set( t << 1, lb, lb + rb >> 1, x ); set( t << 1 | 1, lb + rb >> 1, rb, x ); pull( t ); }; if( ql <= lb and rb <= qr ) return set( t, lb, rb, x ), void(); if( qr <= lb or rb <= ql ) return; push( t, lb, rb ); update( t << 1, lb, lb + rb >> 1, ql, qr, x ); update( t << 1 | 1, lb + rb >> 1, rb, ql, qr, x ); pull( t ); }; update( 1, 0, N, ql, qr, x ); } else { static function< long long( int, int, int, int, int ) > query = [ & ]( int t, int lb, int rb, int ql, int qr ) { if( ql <= lb and rb <= qr ) return score[ t ]; if( qr <= lb or rb <= ql ) return 0LL; push( t, lb, rb ); long long res = query( t << 1, lb, lb + rb >> 1, ql, qr ) + query( t << 1 | 1, lb + rb >> 1, rb, ql, qr ); pull( t ); return res; }; cout << query( 1, 0, N, ql, qr ) << "\n"; } } return 0; }