RangeMinMaxSum
クラス · [区間 l, r) について sum(min(A_i, x)) / sum(max(A_i, x)) を求める
template <class T, class U = T, int L = 30>
struct RangeMinMaxSum;
概要
区間 [l, r) について sum(min(A_i, x)) / sum(max(A_i, x)) を求める
計算量
- 構築は $O(nL)$、問い合わせは $O(L)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空のデータ構造を作る (2) 列 v からデータ構造を構築する |
(1) $O(1)$ (2) $O(nL)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
query_min |
$\sum_{i=l}^{r-1}\min(v_i,x)$ を返す | $O(L)$ |
query_max |
$\sum_{i=l}^{r-1}\max(v_i,x)$ を返す | $O(L)$ |
メンバの詳細
(constructor)
// (1)
RangeMinMaxSum() = default;
// (2)
explicit RangeMinMaxSum(const std::vector<T> &v);
(1) 空のデータ構造を作る
- 計算量: $O(1)$
(2) 列 v からデータ構造を構築する
- 計算量: $O(nL)$