```
1 {-
2
3 Pearl 2: Surpassing
4
5 Definitions:
6 A surpasser of an element of an array (list) is a greater element to the right.
7 x[j] is a surpasser of x[i] if i<j and x[i]<x[j].
8 The surpasser count of an element is the number of its surpassers.
9
10 Problem:
11 Compute the maximum surpasser count of an array of length n>1 in an O(n log n) algorithm.
12
13 Solution:
14
15 Note 1: In the imperative programming, using iterative+binary search.
16 We will use Divide and Conquer
17
18 Note 2: Cannot do better than O(n log n), b/c this is equivalen to sorting (you will see:
19 the table we create)
20 -}
21 module P2 where
22
23 -- Test word is:         GENERATION
24 -- Surpasser count is:   5625140100
25 -- So the maximum isL    6
26 testX = "GENERATION" :: [Char]
27
28 -- Maximum Surpasser Count
29 -- Brute force approach
30 -- Requires O(N^2) steps
31 -- Goes on shrinking list of length n: n+(n-1)+(n-2)+.. = n^2/2
32 msc         ::     Ord a => [a] -> Int
33 msc xs        =    maximum [scount z zs | z:zs <- tails xs]
34 scount x xs    =     length (filter (x<) xs)
35
36 -- We'll redfine tails, to make sure empty returns empty
37 tails             :: [a] -> [[a]]
38 tails []        = []
39 tails (x:xs)    = (x:xs):tails xs
40
41 -- Divide and Conquer
42 -- The trick is to find some 'data' that we can join together
43 -- easily. Then we can divide, and then join.
44 -- There are a few tricks to get to this 'join':
45 -- 1. Define data structure that contains enough information. Then you can join them.
46 --    This data structure is the table, that contains not only the Maximum Surpasser from
47 --    each divide, but all the counts!
48 -- 2. If we keep the Table in sorted order, the join can be done easily! (in Linear time)
49
50 table [x]        =    [(x,0)]        -- one element
51 table xs        =    join' (m-n) (table ys)  (table zs)
52                     where
53                         m = length xs
54                         n = m `div` 2
55                         (ys,zs) = splitAt n xs
56
57 join' 0 txs []    = txs
58 join' n []  tys    = tys
59 join' n txs@((x,c):txs') tys@((y,d):tys')
60         | x<y     = (x,c+n) : join' n txs' tys
61         | x>=y     = (y,d) : join' (n-1) txs tys'
62 -- the lists are ordered within themselves.
63 -- so if x<y ==> All the rest (and there's length n of tys) are also
64 -- greater than x ==> we should add this count!
65 -- if x>y, we just put y.
66 -- if x==y, we just want to make sure we continue in reduced manner, so we put (y,d), remmove
67 -- it from the next join, and then move on to continue.
68
69 -- Main
70
71 main = do
72     putStr "Brute force       : "
73     print \$ msc testX
74     putStr "Divide and Conquer: "
75     print \$ maximum \$ map (snd) (table testX)
```    