1. 理論

1.1. 条件が単調減少の場合

$p\colon 2^{[0, n)} \to 2$ を単調減少な関数とする。($2=\{\mathrm{false}, \mathrm{true}\}$)

$p(\emptyset) = \mathrm{true}$ とする。

• 各区間の左端 l に対して、条件を満たす最大の区間の右端 r を求める場合

  $f\colon [0,n)\to [0,n],\ f(l) = \max\{ r\in [l,n] \mid p[l, r) = \mathrm{true}\}$ は単調増加になっている。

  ($f$ は max_right 関数と言える)

  このような $f$ はしゃくとり法で求められる

  $f$ を使うと以下のことが言える。

  • $p$ を $\mathrm{true}$ にする最長区間はある $l\in [0,n)$ で $[l, f(l))$ と書ける。
    • つまり、最長区間長は $\max_{l\in[0, n)} (f(l) - l)$ である。
  • $p$ を $\mathrm{true}$ にする（空でない）区間の個数は $\sum_{l\in[0,n)} (f(l) - l)$ である

• 各区間の左端 l に対して、条件を満たす最大の区間の右端 r を求める場合

  $g\colon [0,n]\to [0,n),\ g(r) = \min\{ l\in [0,r] \mid p[l, r) = \mathrm{true}\}$ は単調増加になっている。

  （$g$ は min_left 関数と言える）

  このような $f$ はしゃくとり法で求められる

  $g$ を使うと以下のことが言える。

  • $p$ を $\mathrm{true}$ にする最長区間はある $r\in [0,n]$ で $[g(r), r)$ と書ける。
    • つまり、最長区間長は $\max_{r\in[0, n]} (r - g(r))$ である。
  • $p$ を $\mathrm{true}$ にする（空でない）区間の個数は $\sum_{r\in[0,n]} (r - g(r))$ である

1.2. 条件が単調増加の場合

$p\colon 2^{[0, n)} \to 2$ を単調増加な関数とする。($2=\{\mathrm{false}, \mathrm{true}\}$)

このとき、$f\colon [0,n)\to [0,n]\cup\{+\infty\},\ f(l) = \min\{ r\in [l,n] \mid p[l, r) = \mathrm{true}\}$ は単調増加になっている（ただし、$\min \emptyset = +\infty$ とする）

また、以下のことが言える。

• $p$ を $\mathrm{true}$ にする最短区間はある $l\in[0,n)$ で $[l, f(l))$ と書ける。
  • 最短区間長は $\min_{l\in[0,n)} (f(l) - l)$ である。
• $p$ を $\mathrm{true}$ にする（空でない）区間の数は $\sum_{l\in[0,n) f(l) \neq +\infty} (n+1 -f(l))$ である
  • $+\infty$ は $n+1$ 扱いしてもよさそう

2. できること

• 条件の例
  • 単調減少な条件
    • 連続部分列の総和が k 以下
    • 連続部分列の種類数が k 以下
    • 連続部分列が all unique
  • 単調増加な条件
    • 連続部分列の総和が k 以上
    • 連続部分列の種類数が k 以上
• 求められるもの
  • 区間の数え上げ
  • 最大区間長（条件が単調減少のとき）
  • 最小区間長（条件が単調増加のとき）

3. 実装