# 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 )

Interestingly, compiling without -O makes it faster. A different way to handle queries make it faster, and -O is also faster than -O0 now.
• Woah! It is much faster when compiling without -O. There's gotta be a bug in something, the -O* flag "packages" are supposed to be "non-dangerous" meaning they shouldn't include optimizations that potentially make running time worse. This sure seems like a bug. I tested on GHC 7.6.3, what version are you using? – bisserlis Apr 1 '15 at 7:59
• @bisserlis Executing ghc --version gives The Glorious Glasgow Haskell Compilation System, version 7.8.3 – johnchen902 Apr 1 '15 at 9:50
• @bisserlis -O problem solved. See stackoverflow.com/q/29404065/2040040 . It's a pure performance problem now. – johnchen902 Apr 2 '15 at 4:57