1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

//! 並列二分探索。

use super::super::traits::stateful_predicate;

use stateful_predicate::StatefulPred;

/// 並列二分探索を行う。
///
/// 状態によって返り値の異なる述語を考える。
/// 各クエリに対して、初めて偽になる状態の番号を返す。
/// 常に真となる場合、状態の個数を返す。
///
/// # Requirements
/// 状態 $j$ の述語に $x\_i$ を与えたときの返り値を $f\_j(x\_i)$ とする。
/// $f\_j(x\_i)$ が偽となるとき、${}\^\\forall j\' > j$ について $f\_{j\'}(x\_i)$ も偽となる。
///
/// 直感的には、状態が進むにつれて真となる条件が厳しくなる述語を指す。
///
/// # Idea
/// $i$ 番目のクエリについて、区間 $[\\mathrm{ok}\_i, \\mathrm{bad}\_i)$ を管理する。
/// これは、$f\_{\\mathrm{ok}\_i}(x\_i)$ は真、$f\_{\\mathrm{bad}\_i}(x\_i)$
/// は偽になることを意味する。
/// 状態の個数を $m$ として、初期値は $[-1, m)$ とする。
///
/// 状態を進めていきながら、ある $i$ に対して
/// 状態 $j = \\lfloor(\\mathrm{ok}\_i+\\mathrm{bad}\_i)/2\\rfloor$ となったとき、
/// $f\_j(x\_i)$ を計算する。これにより、答えの範囲が半分に絞れる。
/// この一連の計算を $\\log\_2(m)+O(1)$ 回繰り返せばよい。
///
/// 各クエリについて独立に計算するのではなく、
/// 一つの述語を共有して並列に処理することで、計算量を削減できる。
///
/// 毎ループで状態 $m-1$ まで遷移する必要はなく、
/// $f\_j(x\_i)$ を計算したい $i$ が存在する最大の $j$ まで見ればよい。
///
/// # Notes
/// 永続データ構造が作れるのであれば、単にそれを用いて各クエリについて二分探索を行えばよい。
/// また、クエリの個数が少なく、述語の計算コストが高くない場合は、
/// 各々について線形探索を行う方が高速な場合もありうる。
///
/// # Complexity
/// 状態 $0$ から状態 $m-1$ までの遷移を高々 $\\log\_2(m)+O(1)$ 回行う。
/// また、各クエリに対して述語の呼び出しを $\\log\_2(m)+O(1)$ 回行う。
///
/// # Examples
/// ```
/// use nekolib::algo::parallel_bisect;
/// use nekolib::traits::StatefulPred;
///
/// struct Neko(i32);
/// impl Neko {
///     pub fn new() -> Self { Self(0) }
/// }
///
/// /// 状態 `i` において値 `10 * i` を持ち、値 `100` を最終状態とする。
/// /// この値より大きい値に対して真を返す。
/// impl StatefulPred for Neko {
///     type Input = i32;
///     fn count(&self) -> usize { 11 }
///     fn next(&mut self) {
///         if self.0 < 100 { self.0 += 10; }
///     }
///     fn pred(&self, &x: &i32) -> bool { x > self.0 }
///     fn reset(&mut self) { self.0 = 0; }
/// }
///
/// let qs = vec![0, 1, 32, 60, 89, 99, 100, 101, 500];
/// assert_eq!(
///     parallel_bisect(Neko::new(), qs),
///     vec![0, 1, 4, 6, 9, 10, 10, 11, 11]
/// );
/// ```
pub fn parallel_bisect<S: StatefulPred>(
    mut s: S,
    q: Vec<S::Input>,
) -> Vec<usize> {
    let sn = s.count();
    let qn = q.len();
    let mut ok = vec![0; qn];
    let mut bad = vec![sn + 1; qn];

    loop {
        let mut ev = vec![vec![]; sn + 1];
        let mut max = None;
        for i in 0..qn {
            if bad[i] - ok[i] <= 1 {
                continue;
            }
            let mid = ok[i] + (bad[i] - ok[i]) / 2;
            ev[mid].push(i);
            max = Some(max.unwrap_or(0).max(mid));
        }
        if max.is_none() {
            break;
        }

        s.reset();
        for j in 1..=max.unwrap() {
            for &i in &ev[j] {
                if s.pred(&q[i]) {
                    ok[i] = j;
                } else {
                    bad[i] = j;
                }
            }
            s.next();
        }
    }

    bad.into_iter().map(|x| x - 1).collect()
}