CFR 429 D. Tricky Function ( Divide and Conquer, Closest Pair )

題意：
給 A 數列。求 min{ ( j - i )^2 + Sigma( A[ i + 1 .. j ] )^2, 1 ≤ i < j ≤ N }

資料規模：
The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 1e4 ≤ a[i] ≤ 1e4).

解法：
就是求最近點對距離。
發現自己以前的寫法慢到不行，需要精進一個地方，那就是不做 inplace_merge ( O( N lg N ) )，而是把和 x 的中位數的距離在好的範圍內的點收集起來就好。

時間 / 空間複雜度：
O( N lg N )

其他：
發現很大一部分的人都是用這種解法，覺得不能理解：
http://codeforces.com/contest/429/submission/6593023

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = ( int ) 1e5;

int N;
int A[ MAXN ];
ll pfx[ MAXN + 1 ];

ll sqr( ll x ){ return x * x; }

ll rec_solve( vector< pair< ll, ll > > &pnt, int lb, int rb ){
  if( lb + 1 == rb ) return 1LL << 50;
  int mid = lb + rb >> 1;
  ll mx = pnt[ mid ].first;
  ll res = min( rec_solve( pnt, lb, mid ), rec_solve( pnt, mid, rb ) );
  vector< pair< ll, ll > > interesting;
  for( int i = lb; i < rb; ++i ){
    if( sqr( pnt[ i ].first - mx ) < res ){
      interesting.emplace_back( pnt[ i ] );
    }
  }
  sort( interesting.begin(), interesting.end(),
      [ & ]( pair< ll, ll > i, pair< ll, ll > j ){ return i.second < j.second; } );
  vector< pair< ll, ll > > t;
  for( int i = 0; i < interesting.size(); ++i ){
    if( sqr( interesting[ i ].first - mx ) >= res ) continue;
    for( int j = t.size() - 1; j >= 0; --j ){
      ll dx = interesting[ i ].first - t[ j ].first;
      ll dy = interesting[ i ].second - t[ j ].second;
      if( sqr( dy ) >= res ) break;
      res = min( res, sqr( dx ) + sqr( dy ) );
    }
    t.emplace_back( interesting[ i ] );
  }
  return res;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  for( int i = 0; i < N; ++i ){
    pfx[ i + 1 ] = pfx[ i ] + A[ i ];
  }
  vector< pair< ll, ll > > pnt( N );
  for( int i = 1; i <= N; ++i ){
    pnt[ i - 1 ] = make_pair( i, pfx[ i ] );
  }
  sort( pnt.begin(), pnt.end() );
  cout << rec_solve( pnt, 0, N ) << endl;
  return 0;
}