BOJ 23327 - 리그전 오브 레전드

BOJ 23327 - 리그전 오브 레전드

$[l, r]$ 에서 경기를 치룰 때의 합을 식으로 나타내보면

$$ \begin{aligned} \dfrac {\displaystyle \sum_{i=l}^{r} a_i \sum_{j=l}^ra_j-\sum_{i=l}^r a_i^2}2 \end{aligned} $$

이다.

왜냐면 어떤 플레이어 $i$는 $[l,r]$ 의 자신을 제외한 모든 플레이어와 경기를 할 것이고, 그럼 각 $(i, j)$ 쌍이 두 번씩 더해진다.

$(i, i)$ 같이 같은 쌍은 경기가 일어나지 않으므로 제거해줘야 맞으므로 따로 구간합 배열을 만들어 연산에 이용해준다.

void solve() {  
   int n, q;  
   cin >> n >> q;  
   vi a(n), psum(n + 1), psum2(n + 1);  
   fv(a);  
   for (int i = 0; i < n; i++) psum[i + 1] = psum[i] + a[i], psum2[i + 1] = psum2[i] + a[i] * a[i];  
   auto sum = [&](int l, int r) { return psum[r + 1] - psum[l]; };  
   auto sum2 = [&](int l, int r) { return psum2[r + 1] - psum2[l]; };  
   while (q--) {  
      int l, r;  
      cin >> l >> r, l--, r--;  
      cout << (sum(l, r) * sum(l, r) - sum2(l, r)) / 2 << endl;  
   }  
}