Given $n$ closed intervals $[l_i, r_i]$, the objective is to determine the cardinality of the set ${\sum_{i=1}^{n} x_i^2 \mid x_i \in \mathbb{Z}, l_i \leq x_i \leq r_i}$.

Assuming $n \leq 100$ and $r_i \leq 100$, the maximum possible sum is bounded by $10^6$. This permits a state-compression approach using bitsets, where each bit represents the achievability of a specific sum value.

State Represantation

Maintain a bitset reachable where the $k$-th bit is set to 1 if sum $k$ can be formed using the intervals processed so far. Initialize reachable[0] = 1 to indicate that sum 0 is achievable before processing any intervals.

Transition Mechanism

For each interval $[l, r]$, compute a new bitset next by aggrgeating all possible contributions: $$ \text{next} = \bigvee_{x=l}^{r} (\text{reachable} \ll x^2) $$ The left shift operation << effectively adds $x^2$ to all previously achievable sums, while the bitwise OR accumulates all possibilities across the valid range.

Implementation

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<pair<int, int>> ranges(n);
    for (auto& [lo, hi] : ranges) {
        cin >> lo >> hi;
    }
    
    const int MAX_TOTAL = 100 * 100 * 100;  // 1e6 upper bound
    bitset<MAX_TOTAL + 1> prev_state, next_state;
    prev_state[0] = 1;  // Base case: zero sum with zero elements
    
    for (const auto& [lo, hi] : ranges) {
        next_state.reset();
        for (int val = lo; val <= hi; ++val) {
            int square = val * val;
            next_state |= (prev_state << square);
        }
        prev_state = next_state;
    }
    
    cout << prev_state.count() << '\n';
    return 0;
}

Complexity Anaylsis

• Time: $O(n \cdot w \cdot S / 64)$, where $w$ is the average interval width and $S$ is the maximum sum. The factor of 64 reflects the hardware-level parallelism of bitset operations on 64-bit words.
• Space: $O(S)$ bits, approximately $10^6$ bits ($\sim$125 KB), using the rolling array optimization to avoid storing all $n$ intermediate states.

Example Trace

Consider intervals $[1, 2]$ and $[2, 3]$:

1. Initial: reachable = ${0}$
2. After $[1,2]$: Adding $1^2=1$ and $2^2=4$ yields achievable sums ${1, 4}$
3. After $[2,3]$:
   • Adding $2^2=4$ to previous sums: ${5, 8}$
   • Adding $3^2=9$ to previous sums: ${10, 13}$
   • Union: ${5, 8, 10, 13}$

The final count is 4 distinct values.