====== 배열 구간합 놀이 ======

===== 풀이 =====
  * 각 인덱스가 몇개의 구간에 포함되는지를 구하고 나면, 가장 많은 구간에 포함되는 인덱스에 가장 큰 값을 배치하는 그리디한 방법으로 총합을 가장 크게 만들수 있다,
  * 각 인덱스가 몇개의 구간에 포함되는지는, 누적합과 [[ps:계차수열 트릭]]을 이용해서 O(m+n)에 쉽게 구할수 있다.
  * 추가적으로 구해야 하는 것은, 최댓값을 달성하는 배치 방법의 갯수이다. 포함되는 구간의 갯수가 같은 인덱스끼리는 서로 교환해도 총합이 동일하다. 따라서 포함되는 구간의 개수가 같은 인덱스들을 그룹으로 묶어준 다음에, 각 그룹에 대해서 그룹크기의 팩토리얼을 계산해서 곱해주면, 총합을 동일하게 유지하는 배치방법의 개수가 구해진다
  * 총 시간복잡도는 O(m+n) + O(nlogn) + O(n) = O(m+nlogn)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 24838. 배열 구간합 놀이".

- Problem link: https://www.acmicpc.net/problem/24838
- Solution link: http://www.teferi.net/ps/problems/boj/24838
"""

import collections
import math
import sys

MOD = 10**9 + 7


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        n, m = [int(x) for x in sys.stdin.readline().split()]
        count_delta = [0] * (n + 1)
        A = [int(x) for x in sys.stdin.readline().split()]
        for _ in range(m):
            x, y = [int(x) for x in sys.stdin.readline().split()]
            count_delta[x - 1] += 1
            count_delta[y] -= 1

        v = 0
        add_count = [v := v + x for x in count_delta]
        add_count.pop()
        max_sum = sum(x * y for x, y in zip(sorted(A), sorted(add_count)))
        counter = collections.Counter(add_count)
        arrangement_count = (
            math.prod(math.factorial(v) % MOD for v in counter.values()) % MOD
        )
        print(max_sum, arrangement_count)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}