CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

題意：
給一個長度為 N 的陣列，用顏色描述。要求對於所有 K <- [ 1, N ] 輸出，分割成連續區間，使得每個區間不超過 K 個顏色，最少的區間數量。

資料規模：
N ≤ 1e5

解法：
據說這可以用資料結構 ( 樹狀數組 ) 直接做掉，但我看不懂。
首先答案一定是非嚴格遞減的。
這題的重點在於看透一個結論：「答案的種類大約在 N^0.5 級別」。
原因是，當 K ≤ N^0.5 時，至多有 N^0.5 種答案。但當 K > N^0.5 時，由於一個區間至少可以涵蓋 N^0.5 這麼長的區間，因此最多的最少區間數量至多也是 N^0.5。
有了這個結論後，可以做一種很特別的剪枝的分治法。
剪枝的方法是這樣的：若當前左界和右界的答案是相同的，那麼直接將這個區間都劃記為該答案，並立刻結束這個區間的計算。否則，計算中間的答案，並分治為兩個規模相同的子問題。計算答案的部分用爬行法線性處理即可。由於計算答案的次數至多為答案種類的數量，一次計算的花費至多為 O( N )，所以可以得出這個做法的複雜度為 O( N^1.5 )。

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

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

const int MAXN = ( int ) 1e5;

int N;
int A[ MAXN ];

int ans[ MAXN + 1 ];

int calc( int k ){
  static vector< int > cnt( MAXN + 1 );
  int res = 0;
  for( int i = 0; i < N; ){
    ++res;
    int j = i;
    int f = 0;
    while( j < N and f <= k ){
      if( f == k and cnt[ A[ j ] ] == 0 ) break;
      f += ++cnt[ A[ j++ ] ] == 1;
    }
    while( i < j ){
      --cnt[ A[ i++ ] ];
    }
  }
  return res;
}

void dvcq( int lb, int rb ){ // ( lb, rb )
  if( rb - lb < 2 ) return;
  if( ans[ lb ] == ans[ rb ] ){
    for( int i = lb + 1; i < rb; ++i ){
      ans[ i ] = ans[ lb ];
    }
    return;
  }
  int mid = lb + rb >> 1;
  ans[ mid ] = calc( mid );
  dvcq( lb, mid );
  dvcq( mid, rb );
}

signed main(){
  ios::sync_with_stdio( 0 );
  { // input
    cin >> N;
    for( int i = 0; i < N; ++i ){
      cin >> A[ i ];
    }
  }
  {
    ans[ 1 ] = calc( 1 );
    ans[ N ] = calc( N );
    dvcq( 1, N );
  }
  {
    for( int i = 1; i <= N; ++i ){
      cout << ans[ i ] << " \n"[ i == N ];
    }
  }
  return 0;
}