# CFR 444 C. DZY Loves Colors ( Segment Tree, Dummy Constraints )

Problem - 444C - Codeforces

M 筆詢問，兩種形式：
1 l r x：將 [ l, r ] 都塗色為 x
2 l r：輸出 [ l, r ] 的貢獻總和

1 ≤ N, M ≤ 1e5
1 ≤ X ≤ 1e8

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;
}
```