각 $q_i$에 대해서 다음을 구하는 문제입니다.
$$\sum_{j = 1}^{N} a_j\left| q_i-x_j \right| $$
절댓값을 그대로 계산하면 $O\left(N\right)$으로 전체 시간복잡도가 $O\left(NQ\right)$가 됩니다.
절댓값의 특성을 생각해보면 $q_i$보다 작은 $x_j$에 대해서는 $a_j\left(q_i-x_j\right)$를, $q_i$보다 큰 $x_j$에 대해서는 $a_j\left(x_j-q_i\right)$을 계산하면 됩니다.
이를 바탕으로 위 식을 다시 적으면 이렇게 됩니다.
$$q_i\sum_{x_j\lt q_i} a_j - \sum_{x_j\lt q_i} a_jx_j + \sum_{x_j\ge q_i} a_jx_j - q_i\sum_{x_j\ge q_i} a_j$$
$\left\lbrace x_j\right\rbrace$를 미리 정렬해두면 $x_j\lt q_i$인 $j$를 $O\left(\log N\right)$에 구할 수 있고, $a_j$와 $a_jx_j$의 누적 합을 전처리하여 구간 합을 $O\left(1\right)$에 구할 수 있습니다.
따라서 전체 시간복잡도 $O\left(Q\log N\right)$에 답을 구할 수 있습니다.
코드
fn solve(data: &mut [(i64, i64)], query: impl Iterator<Item = i64>, out: &mut impl Write) {
data.sort_unstable();
let mut n_people_sum = vec![0; data.len() + 1];
let mut distance_sum = vec![0; data.len() + 1];
for i in 0..data.len() {
n_people_sum[i + 1] = n_people_sum[i] + data[i].1;
distance_sum[i + 1] = distance_sum[i] + data[i].1 * data[i].0;
}
for candidate in query {
let partition = data.partition_point(|&(pos, _)| pos < candidate);
let left_sum = candidate * n_people_sum[partition] - distance_sum[partition];
let right_sum = distance_sum[data.len()]
- distance_sum[partition]
- candidate * (n_people_sum[data.len()] - n_people_sum[partition]);
writeln!(out, "{}", left_sum + right_sum);
}
}