Persistent segment tree

I'm trying to solve this problem.

Given a sequence \$B=B_0,B_1,\ldots,B_{N−1}\$ for each query \$(P,K)\$, find the minimum \$S\$ s.t. there are at least \$K\$ entries in \$B\$ that satisfies

• \$\left|P−i\right| \le S\$
• \$B_i \le S\$

where \$B_i\$ denotes the \$i^{th}\$ entry of \$B\$.

Input

The first line contains two integers \$N, M\$.
The second line the \$N\$ space-delimited integers of the sequence \$B\$.
The following \$M\$ lines are \$M\$ queries and each query is consists of two integers \$P,K\$.

Output

For each query, you should output one integer.

Constraints

$$\begin{array}{rcl} 1 &\le N &\le 10^5 \\ 1 &\le M &\le 10^5 \\ 1 &\le B_i &\le N \\ 0 &\le P &< N \\ 1 &\le K &\le N \\ \end{array}$$

My solution uses binary search and persistent segment tree. The algorithm should be correct because I've implemented it in C++ and it's accepted.

import Control.Monad
import Data.Array

data Node =
      Leaf   Int           -- value
    | Branch Int Node Node -- sum, left child, right child
type NodeArray = Array Int Node

-- create an empty node with range [l, r)
create :: Int -> Int -> Node
create l r
    | l + 1 == r = Leaf 0
    | otherwise  = Branch 0 (create l m) (create m r)
    where m = (l + r) `div` 2

-- Get the sum in range [0, r). The range of the node is [nl, nr)
sumof :: Node -> Int -> Int -> Int -> Int
sumof (Leaf val) r nl nr
    | nr <= r   = val
    | otherwise = 0
sumof (Branch sum lc rc) r nl nr
    | nr <= r   = sum
    | r  > nl   = (sumof lc r nl m) + (sumof rc r m nr)
    | otherwise = 0
    where m = (nl + nr) `div` 2

-- Increase the value at x by 1. The range of the node is [nl, nr)
increase :: Node -> Int -> Int -> Int -> Node
increase (Leaf val) x nl nr = Leaf (val + 1)
increase (Branch sum lc rc) x nl nr
    | x < m     = Branch (sum + 1) (increase lc x nl m) rc
    | otherwise = Branch (sum + 1) lc (increase rc x m nr)
    where m = (nl + nr) `div` 2

-- signature said it all
tonodes :: Int -> [Int] -> [Node]
tonodes n = reverse . tonodes' . reverse
    where
        tonodes' :: [Int] -> [Node]
        tonodes' (h:t) = increase h' h 0 n : s' where s'@(h':_) = tonodes' t
        tonodes' _ = [create 0 n]

-- find the minimum m in [l, r] such that (predicate m) is True
binarysearch :: (Int -> Bool) -> Int -> Int -> Int
binarysearch predicate l r
    | l == r      = r
    | predicate m = binarysearch predicate l m
    | otherwise   = binarysearch predicate (m+1) r
    where m = (l + r) `div` 2

-- main, literally
main :: IO ()
main = do
    [n, m] <- fmap (map read . words) getLine
    nodes <- fmap (listArray (0, n) . tonodes n . map (subtract 1) . map read . words) getLine
    mapM_  (print . solve n nodes) =<< (replicateM m $ fmap (map read . words) getLine)
    where
        solve :: Int -> NodeArray -> [Int] -> Int
        solve n nodes [p, k] = binarysearch ok 0 n
            where
                ok :: Int -> Bool
                ok s = (sumof (nodes ! min (p + s + 1) n) s 0 n) - (sumof (nodes ! max (p - s) 0) s 0 n) >= k

This is my random input generator in C++:

#include <cstdio>
#include <cstdlib>
using namespace std;
int main (int argc, char * argv[]) {
    srand(1827);
    int n = 100000;
    if(argc > 1)
        sscanf(argv[1], "%d", &n);
    printf("%d %d\n", n, n);
    for(int i = 0; i < n; i++)
        printf("%d%c", rand() % n + 1, i == n - 1 ? '\n' : ' ');
    for(int i = 0; i < n; i++) {
        int p = rand() % n;
        int k = rand() % n + 1;
        printf("%d %d\n", p, k);
    }
}

This is the result on my computer:

$ ghc -fforce-recomp -O 1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ time ./gen.exe 100000 | ./1827.exe > /dev/null
real    0m4.389s
user    0m0.046s
sys     0m0.030s

It should complete in no more than 2 seconds. Can you provide suggestions about speed or general practice?

Interestingly, compiling without -O makes it faster. A different way to handle queries make it faster, and -O is also faster than -O0 now.