The number of integers on the blackboard can be up to \(10^{11}\), so if you add the integers on the blackboard one by one, you will get TLE. Therefore, it is important to sum them up in a smart way.

A. Gather the numbers written in an operation

The sum of all integers between \(1\) and \(x\), inclusive, can be calculated by \(\dfrac{x(x+1)}2\). From this formula, you can derive the following formula:

( The sum of all integers between \(A\) and \(B\), inclusive ) \(=\) ( The sum of all integers between \(1\) and \(B\), inclusive ) \(-\) ( The sum of all integers between \(1\) and \(A-1\), inclusive ) \(=\dfrac{B(B+1)}2-\dfrac{A(A-1)}2\).

By totaling them, the problem can be solved in a total of \(O(N)\) time.

Note that the answer may not be fit in a 32-bit integer.

Sample Code (C++)

#include <iostream>
using namespace std;
using ll = int64_t;

int main(){
    ll n;
    cin >> n;
    ll ans = 0;
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        ans += b * (b + 1) / 2 - a * (a - 1) / 2;
    }
    cout << ans << endl;
}

Sample code (Python)

n = int(input())
ans = 0
for i in range(n):
    a, b = map(int, input().split())
    ans += b * (b + 1) // 2 - a * (a - 1) // 2
print(ans)

B. Gather the same integers

Since \(1 \leq A_i \leq B_i \leq 10^6\), if you know how many times each number is written, the total sum can be calculated fast.

Consider an array \(cnt[i]=\) (The number of \(i\) written on the blackboard). Initially, \(cnt[i] = 0\).

An operation can be considered as an operation of adding 1 from \(cnt[A]\) to \(cnt[B]\). This can be optimized by cumulative sums, so it can be solved in a total of \(O(N+\max(B))\) time.

Sample Code (C++)

#include <iostream>
#include <vector>
using namespace std;
using ll = int64_t;

int main(){
    ll n;
    cin >> n;
    vector<ll> cnt(1000002);
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b + 1]--;
    }
    for(ll i = 0; i + 1 < cnt.size(); i++) cnt[i + 1] += cnt[i];
    ll ans = 0;
    for(ll i = 0; i < cnt.size(); i++) ans += cnt[i] * i;
    cout << ans << endl;
}