関数プログラミング珠玉のアルゴリズムデザイン上位者問題

文字列で各文字の右側にその文字より大きい文字が何回出てくるか数える、が第二章のお題らしい
何に使うの？それ

i < jかつx[i] < x[j]のカウントなんだとさ
"GENERATING"という文字列なら各文字の上位者数は
[5625140100]になるらしい

こいつをO(n log n)で計算しろと
こいつは解を見なくても簡単に分かった
どうせ全部チェックしないといけないのだから文字列の後ろから上位者数を計算していく

まず最初
"GENERATING"なら末尾の"G"、こいつを配列に移動する[G]、上位者数は0
"GENERATIN" [G]を見て次の"N"を配列のどこに入れたらいいか考える、一番後ろ(配列1の位置)なので上位者数は配列数-1で0
"GENERATI" [GN]を見て次の"I"を配列のどこに入れたらいいか考える、配列1の位置なので上位者数は配列数-1で1
"GENERAT" [GIN]を見て次の"T"を配列のどこに入れたらいいか考える、一番後ろなので上位者数は配列数-3で0
"GENERA" [GINT]を見て次の"A"を配列のどこに入れたらいいか考える、配列0の位置なので上位者数は配列数-0で4
"GENER" [AGINT]を見て次の"R"を配列のどこに入れたらいいか考える、配列4の位置なので上位者数は配列数-4で1
"GENE" [AGINRT]を見て次の"E"を配列のどこに入れたらいいか考える、配列1の位置なので上位者数は配列数-1で5
"GEN" [AEGINRT]を見て次の"N"を配列のどこに入れたらいいか考える、配列5(*1)の位置なので上位者数は配列数-5で2
"GE" [AEGINNRT]を見て次の"E"を配列のどこに入れたらいいか考える、配列2の位置なので上位者数は配列数-2で6
"G" [AEEGINNRT]を見て次の"G"を配列のどこに入れたらいいか考える、配列4の位置なので上位者数は配列数-4で5
終わり
配列は必ずソート済みなので二分探索でよろしい
ソート済み配列に突っ込む位置を要素数から引くと上位者数となっちゃうよ、と
二分探索なのでO(n log n)でしょっ、と
*1) 同じ文字があったらケツにブチ込む

で、本に書いてあった分割統治法による解がこれ

table [x] = [(x, 0)]
table xs  = join (m - n) (table ys) (table zs)
            where m        = length xs
                  n        = m div 2
                  (ys, zs) = splitAt n xs

join 0 txs [] = txs
join n [] tys = tys
join n txs@((x, c) : txs') tys@((y, d) : tys')
   | x <  y = (x, c + n) : join n txs' tys
   | x >= y = (y, d)     : join (n - 1) txs tys'

・・・(；ﾟДﾟ)
よ、、、よめない

で、ホントに何に使うの？これ