(* Basic Fenwick implementation *) (* Also sometimes called a Range Rree *) (* Here's how this works. Consider the binary represented integers 1, 2, .... n. Let's define two functions on these: UP and DN. UP(i) = i + (i land (-i)) DN(i) = i - (i land (-i)) (Here "land" is the bitwise and operation.) It's easy to see what these functions do when we look at the binary representation of i. i land (-i) simply extracts the rightmost 1 bit of i. So DN(i) just takes the rigthmost 1 bit of i and zeros it. UP(i) takes the rightmost 1 bit of i, zeros it, and carries a 1 to the left. UP() is a strictly increasing function and DN() is strictly decreasing. let UP-PATH(a) be the sequence [a, UP(a), UP(UP(A))...] terminating right before it exceeds n. Similarly let DN-PATH(b) be [b, DN(b), ...] terminating right before it reaches 0. Theorem: if a <= b then UP-PATH(a) and DN-PATH(b) intersect at precisely one point. furthermore if a>b then these sets have no intersection. Proof: The 2nd part is clear because all elements of UP-PATH(a) are >=a and all elements of DN-PATH(b) are <= b. The result follows. Similarly if a=b then the two paths clearly intersect only at a. If aj. Here are a couple of additional observations. First of all it's possible to generalize this scheme to make shorter UP-PATHS and longer DN-PATHS. For example by using base 4, we can make the UP-PATHS log_4(n) and the DN-PATHS 3*log_4(n). If we use base b, then the two bounds are log_b(n) and (b-1)*log_b(n). An interesting extreme case is b = sqrt(n). In this case the UP-PATHS are length 2, and the down paths are length 2*sqrt(n). This kind of approach is useful if there are a lot more Increments than SumToLeft operations. (Or vice versa, see below.) Another observation is that the theorem about these paths having a unique intersection when a=m then (m,bit) else ( bit.(i) <- bit.(i) + v; loop (i + (i land (-i))) ) in loop i let lookup (m,bit) i = let rec loop i ac = if i=0 then ac else loop (i - (i land (-i))) (ac + bit.(i)) in loop i 0 (*************************************************************) open Printf open Scanf let ( ++ ) a b = Int64.add a b let long x = Int64.of_int x let read_int () = bscanf Scanning.stdib " %d " (fun x -> x) let read_string () = bscanf Scanning.stdib " %s " (fun x -> x) let () = let n = read_int() in let a = read_string() in let b = read_string() in let toind a i = (int_of_char a.[i-1]) - (int_of_char 'A') in let q = Array.make 26 [] in let perm = Array.make (n+1) 0 in for i=1 to n do q.(toind a i) <- i::q.(toind a i) done; for i=n downto 1 do perm.(i) <- List.hd q.(toind b i); q.(toind b i) <- List.tl q.(toind b i) done; let rec loop f i ac = if i = 0 then ac else let ac = ac ++ (long (lookup f perm.(i))) in loop (insert f 1 perm.(i)) (i-1) ac in printf "%Ld\n" (loop (init n) n 0L)