0w1

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

Problem - 444C - Codeforces

題意:
給長度 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;
}