ARC 074 D - 3N Numbers ( Segment Tree )

D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder

題意：
給長度 3 * N 的數列 A[]。刪除 N 個元素後，希望前 N 個元素總和 - 後 N 個元素總和最大。

制約：
N ≤ 1e5
1 ≤ A[ i ] ≤ 1e9

解法：
考慮一條線，從 N 掃描到 2 * N。
這條線會將數列分成兩塊，此時我們想知道左邊那塊最大的 N 個元素總和 - 右邊那塊最小的 N 個元素總和是多少。
這東西只要對數值先離散化，就能用線段樹維護。

複雜度：
O( N lg N )

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1 << 19;
 
int N;
int A[ MAXN * 3 ];
vector< int > dsctz;
map< int, int > dmp;
 
struct segt {
  long long sum[ MAXN << 2 ];
  int cnt[ MAXN << 2 ];
  void pull( int t ) {
    sum[ t ] = sum[ t << 1 ] + sum[ t << 1 | 1 ];
    cnt[ t ] = cnt[ t << 1 ] + cnt[ t << 1 | 1 ];
  }
  void modify( int t, int lb, int rb, int k, int v ) {
    if( lb + 1 == rb ) {
      sum[ t ] += v * dsctz[ lb ];
      cnt[ t ] += v;
      return;
    }
    int mid = lb + rb >> 1;
    if( k < mid ) modify( t << 1, lb, mid, k, v );
    else modify( t << 1 | 1, mid, rb, k, v );
    pull( t );
  }
  long long dfs_max( int t, int lb, int rb, int k ) {
    if( lb + 1 == rb ) {
      return 1LL * dsctz[ lb ] * k;
    }
    int mid = lb + rb >> 1;
    if( cnt[ t << 1 | 1 ] >= k ) return dfs_max( t << 1 | 1, mid, rb, k );
    return dfs_max( t << 1, lb, mid, k - cnt[ t << 1 | 1 ] ) + sum[ t << 1 | 1 ];
  }
  long long dfs_min( int t, int lb, int rb, int k ) {
    if( lb + 1 == rb ) {
      return 1LL * dsctz[ lb ] * k;
    }
    int mid = lb + rb >> 1;
    if( cnt[ t << 1 ] >= k ) return dfs_min( t << 1, lb, mid, k );
    return sum[ t << 1 ] + dfs_min( t << 1 | 1, mid, rb, k - cnt[ t << 1 ] );
  }
} root[ 2 ];
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < 3 * N; ++i ) {
    cin >> A[ i ];
    dsctz.emplace_back( A[ i ] );
  }
  sort( dsctz.begin(), dsctz.end() );
  dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() );
  for( int i = 0; i < dsctz.size(); ++i ) {
    dmp[ dsctz[ i ] ] = i;
  }
  for( int i = 0; i < N; ++i ) {
    root[ 0 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], 1 );
  }
  for( int i = 3 * N - 1; i >= N; --i ) {
    root[ 1 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], 1 );
  }
  long long ans = root[ 0 ].dfs_max( 1, 0, dsctz.size(), N ) - root[ 1 ].dfs_min( 1, 0, dsctz.size(), N );
  for( int i = N; i < 2 * N; ++i ) {
    root[ 0 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], 1 );
    root[ 1 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], -1 );
    ans = max( ans, root[ 0 ].dfs_max( 1, 0, dsctz.size(), N ) - root[ 1 ].dfs_min( 1, 0, dsctz.size(), N ) );
  }
  cout << ans << endl;
  return 0;
}