백준 23327 (리그전 오브 레전드)

https://www.acmicpc.net/problem/23327

23327번: 리그전 오브 레전드

어떤 쿼리가 주어질때 그게 만약 연속된 어떤 것을 구하는 거라면 그게 누적합으로 접근 할 수 있겠구나를 느꼈다.
머 사실 N, Q = 10^5이고, 1초인데 O(N*Q)는 불가능하니 O(Q)일텐데 먼가 전처리가 필요하겠구나 싶은 문제이다.

그래서 전처리를 해보자

전처리를 하기 전에 뚝딱 하다보면 수식이 하나 나온다.

sum(l..r)*r+1 은 r+1과 l~r 끼리의 재미의 합이다.
그 전에 재미의 합을 계속해서 더 해서 저장한 뒤에
sum과 현재의 값을 통해서 0에서 지금까지 재미의 합을 구할 수 있다.

그러면 진짜 재미의 합(l..r) 은 어떻게 구하냐하면

이것도 앞서 저장한 값들을 이용한다.

l...r 까지의 재미의 합은 0부터 r까지의 재미의 합에서
l부터 r까지와 0부터 l-1까지 대결했을 때 재미를 빼고,

즉 (l + (l+1) + (l+2) + .. + r) * (0 + 1 + 2 + .. + (l-1))
0부터 l-1까지의 재미를 빼면 정답이 나온다.

이것도 매우 흥미롭게 풀었다.

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
const int MAX = 100'005;
const int INF = 1e9 + 1;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

ll sum[MAX];
ll ans[MAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        ll a;
        cin >> a;
        if(i==0){
            sum[i] = a;
            ans[i]=0;
        }
        else {
            sum[i] = sum[i-1]+a;
            ans[i] = ans[i-1] + a*sum[i-1];
        }
    }
    for(int i=0; i<Q; i++){
        int a, b;
        cin >> a >> b;
        if(a==1)cout << ans[b] <<'\n';
        else cout << ans[b] - (sum[b]-sum[a-1])*sum[a-1] - ans[a-1] <<'\n';
    }
}