How many triangles exists? Prefix sum problem

cf_how_many_triangles.md

Interesting problem in prefix sums cf.

Given a, b, c, d find how many triangles with sides (x, y, z) exist such that a <= x <= b <= y <= c <= z <= d. The idea of the solution is to sum up prefix sum as described in the comment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N = 1e6 + 77;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<ll> prefSum(N);
    for (ll i = a; i <= b; ++i) {
        ++prefSum[i + b];    
        --prefSum[i + c + 1];
    }
    for (ll i = 1; i < N; ++i)
        prefSum[i] += prefSum[i-1];
    
    // Normal prefix sum gives how many pairs (x, y) exists such that x + y == i
    // But what we want is to compute how many pairs such that x + y > i exist
    // So do another time prefix summing, in this case required can be computed as prefSum[inf] - prefSum[i-1]
    for (ll i = 1; i < N; ++i)
        prefSum[i] += prefSum[i-1];
    
    // go over all possible z and add up how many ways to choose x + y > z
    ll res = 0;
    for (ll z = c; z <= d; ++z)
        res += prefSum.back() - prefSum[z];
    
    cout << res << endl;
    
    return 0;
}