# ARC 074 D - 3N Numbers ( Segment Tree )

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

N ≤ 1e5
1 ≤ A[ i ] ≤ 1e9

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