합

$n=R-L+1$이라고 하자.

정확히 $k$개의 수를 선택하여 만들 수 있는 합을 생각하자. 가장 작은 합과 가장 큰 합은 각각

$$\operatorname{lo}_k=kL+\frac{k(k-1)}2, \qquad \operatorname{hi}_k=kR-\frac{k(k-1)}2$$

이다. 연속한 정수에서 서로 다른 $k$개를 선택하면 이 두 값 사이의 모든 정수 합을 만들 수 있다. 따라서 정확히 $k$개를 선택하여 만들 수 있는 합은 정수 구간 $I_k=[\operatorname{lo}_k,\operatorname{hi}_k]$를 이룬다.

$k$가 증가하면 각 구간의 왼쪽 끝점과 오른쪽 끝점이 모두 증가한다. 그러므로 모든 구간 길이의 합에서 이웃한 두 구간이 겹치는 길이를 빼면 합집합의 크기를 얻을 수 있다.

구간 $I_k$의 길이는

$$\operatorname{hi}_k-\operatorname{lo}_k+1=k(n-k)+1$$

이다. 모든 구간 길이의 합은

$$\sum_{k=1}^{n}(k(n-k)+1)=\frac{n(n+1)(n-1)}6+n$$

이다.

$I_k$와 $I_{k+1}$이 겹치는 길이는

$$\max(0,\operatorname{hi}_k-\operatorname{lo}_{k+1}+1) =\max(0,k(n-1-k)-L+1)$$

이다. 양수가 되는 조건은

$$k(n-1-k)\geq L$$

이다.

$k(n-1-k)$는 대칭이며 $k=1,2,\ldots,\lfloor(n-1)/2\rfloor$에서 증가한다. 이분 탐색으로 조건을 처음 만족하는 값 를 찾으면 조건을 만족하는 전체 범위는

$$a\leq k\leq n-1-a$$

이다. 조건을 만족하는 값이 없다면 겹치는 길이의 합은 $0$이다.

$b=n-1-a$라고 할 때, 빼야 할 길이의 합은

$$\sum_{k=a}^{b}\left(k(n-1-k)-L+1\right) =(n-1)\sum_{k=a}^{b}k-\sum_{k=a}^{b}k^2-(L-1)(b-a+1)$$

이다. $\sum k$와 $\sum k^2$의 공식을 사용해 $O(1)$에 계산할 수 있다.

모든 계산을 $10^9+7$로 나누어 처리한다. 이분 탐색에서 곱을 비교할 때는 64비트 범위를 안전하게 처리하기 위해 128비트 정수를 사용한다.

테스트 케이스 하나당 시간 복잡도는 $O(\log(R-L+1))$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT6