백준 문제 23327번 리그전 오브 레전드 문제풀이 c++

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

23327번: 리그전 오브 레전드

문제해석 

각각의 후보 디비전수만큼 입력받은 l과 r에대해 l번째 팀부터 r번째까지의 모든 경기 대진의 재미의 합을 구하는것이다

경기하나의 재미는 두 팀의 재미의 곱이다.

단순하게 l부터 r까지 반복문을 돌리게되면 시간제한이 1초인데 1억번은 가볍게 넘기기 때문에 시간초과가 나기때문에 다른 방법을 생각해보아야한다.

 

그렇다면 몇가지 예를 들어보면서 규칙적인 무언가가 있는지 찾아보았는데

예를 들어 5팀이 참여하고 순서대로 5 1 2 3 2의 재미를 가지고있고 l=1, r=5라면

5*1+5*2+5*3+5*2=40

1*2+1*3+1*2=7

2*3+2*2=10

3*2=6

40+7+10+6=63만큼의 재미가 나온다.

l=1, r=4일경우

5*1+5*2+5*3=30

1*2+1*3=5

2*3=6

30+5+6=41만큼의 재미가 나온다.

l=2, r=4 경우

1*2+1*3=5

2*3=6

5+6=11만큼의 재미가 나온다.

뭔가 나열을 하다보니 다음 그림과 같은 규칙을 찾을 수 있었다.

s1+s2+...sn-1은 1번째팀부터 n번째 팀을 선택했을 경우 해당하는 재미이다.

l=2, r=4를 선택 했을경우를 보면 그림 상에서 아래에 해당한다.

그림이 조잡하지만 이해 하는데 문제는 없을것 같다.

전체에서 파란색부분과 주황색 부분을 빼주면 초록 부분만 남는다.

단 여기서 주황부분과 파란부분의 교집합에 해당하는부분이 두번 빼주게 되니

그에 해당하는 부분인 보라색 부분을 더해 주면된다

즉 초록색=전체-주황색-파란색+보라색을 하면 되니까 필요한 부분의 누적 합 배열을 만들어 주면된다.

이런 아이디어를 바탕으로 아래와 같은 코드를 작성하여 풀었다.

 

코드

#include <iostream>
using namespace std;
long long int popular[100005];
long long int sum[100005];
long long int length[100005];
long long int width[100005];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,q,l,r;
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>popular[i];
        sum[i]=sum[i-1]+popular[i];
    }
    for(int i=n; i>=2; i--)
    {
        length[i-1]=length[i]+popular[i]*(sum[i-1]);
    }
    for(int i=1; i<=n-1; i++)
    {
        width[i]=width[i-1]+popular[i]*(sum[n]-sum[i]);
    }
    for(int i=0; i<q; i++)
    {
        cin>>l>>r;
        cout<<width[n-1]-width[l-1]-length[r]+sum[l-1]*(sum[n]-sum[r])<<"\n";
    }
}