algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit 4a295f48251d0a22a4cc5e8eb177fc638ccb53af
parent 8f79a0a319f855ae75a9009e4a81d6cbb6d8cde1
Author: Andrew Laack <andrew@laack.co>
Date:   Thu, 12 Nov 2026 12:20:29 -0600

Prefix sum and range query soln. in ocaml

Diffstat:
Acomp/kuriyama-mirais-stones/ex1.in | 6++++++
Acomp/kuriyama-mirais-stones/main.ml | 85+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/kuriyama-mirais-stones/problem.txt | 51+++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 142 insertions(+), 0 deletions(-)

diff --git a/comp/kuriyama-mirais-stones/ex1.in b/comp/kuriyama-mirais-stones/ex1.in @@ -0,0 +1,6 @@ +6 +6 4 2 7 2 7 +3 +2 3 6 +1 3 4 +1 1 6 diff --git a/comp/kuriyama-mirais-stones/main.ml b/comp/kuriyama-mirais-stones/main.ml @@ -0,0 +1,85 @@ +(* +- n stones +- 1 -> n +- cost of ith is v_i +- query types + 1. sum + - l,r + - l <= r + - sum from l to r + 2. u_i cost of ith cheapest stone l and r where we sum over these + - basically, sum on ordered list non-decreasing + +- n, n integers (costs), m (number of questions), questions (type, l, r) + +n = 6 +costs = 6 4 2 7 2 7 +question count = 3 + +q1 = 2 3 6 +q2 = 1 3 4 +q3 = 1 1 6 + +2 3 6 is ordered sum from index 2 to 5 + +[2, 2, 4, 6, 7, 7] + +sum(4, 6, 7, 7) = 24 + +... + +*) + +type query = {tp : int64; l : int; r : int} + +let readShortInt () = + Scanf.scanf " %d" (fun x -> x) + +let readInt () = + Scanf.scanf " %Ld" (fun x -> x) + +let readInts num = + let arr = Array.make num (Int64.zero) in + let rec acc itr = + if itr == num then () + else (arr.(itr) <- readInt (); acc (itr+1)) + in let () = acc 0 in arr + + +let readQuery () = + let a = readInt () in let b = readShortInt () in let c = readShortInt () in + {tp = a; l = b; r = c} + +let readQueries qc = + let arr = Array.make qc {tp = 0L; l = 0; r = 0} in + let rec acc idx = + if idx = qc then () else (arr.(idx) <- readQuery (); acc (idx+1)) + in acc 0; arr + +let prefixSums arr = + let sums = Array.make ((Array.length arr) + 1) Int64.zero in + let rec acc idx running = + if idx = Array.length arr then () + else (sums.(idx+1) <- (Int64.add running arr.(idx)); acc (idx+1) (Int64.add running arr.(idx))) + in acc 0 0L; sums + +let handleQuery query orderedSums stdSums = + if query.tp = 2L then + (print_endline (Int64.to_string (Int64.sub orderedSums.(query.r) orderedSums.(query.l-1)))) + else + (print_endline (Int64.to_string (Int64.sub stdSums.(query.r) stdSums.(query.l-1)))) + +let rec handleQueries queries orderedSums stdSums idx = + if idx = Array.length queries then () + else + (handleQuery queries.(idx) orderedSums stdSums; handleQueries queries orderedSums stdSums (idx+1)) + +let () = + let n = readShortInt () in + let costs = readInts n in + let stdSums = prefixSums costs in + let () = Array.sort compare costs in + let orderedSums = prefixSums costs in + let qc = readShortInt () in + let queries = readQueries qc in + handleQueries queries orderedSums stdSums 0 diff --git a/comp/kuriyama-mirais-stones/problem.txt b/comp/kuriyama-mirais-stones/problem.txt @@ -0,0 +1,51 @@ +B. Kuriyama Mirai's Stones +time limit per test +2 seconds +memory limit per test +256 megabytes + +Kuriyama Mirai has killed many monsters and got many (namely n) stones. She numbers the stones from 1 to n. The cost of the i-th stone is vi. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions: + + She will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her . + Let ui be the cost of the i-th cheapest stone (the cost that will be on the i-th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her . + +For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy. +Input + +The first line contains an integer n (1 ≤ n ≤ 105). The second line contains n integers: v1, v2, ..., vn (1 ≤ vi ≤ 109) — costs of the stones. + +The third line contains an integer m (1 ≤ m ≤ 105) — the number of Kuriyama Mirai's questions. Then follow m lines, each line contains three integers type, l and r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), describing a question. If type equal to 1, then you should output the answer for the first question, else you should output the answer for the second one. +Output + +Print m lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input. + +--- + +- n stones +- 1 -> n +- cost of ith is v_i +- query types + 1. sum + - l,r + - l <= r + - sum from l to r + 2. u_i cost of ith cheapest stone l and r where we sum over these + - basically, sum on ordered list non-decreasing + +- n, n integers (costs), m (number of questions), questions (type, l, r) + +n = 6 +costs = 6 4 2 7 2 7 +question count = 3 + +q1 = 2 3 6 +q2 = 1 3 4 +q3 = 1 1 6 + +2 3 6 is ordered sum from index 2 to 5 + +[2, 2, 4, 6, 7, 7] + +sum(4, 6, 7, 7) = 24 + +...