We are essentially asked to compute the number of pairs of lattice points $(x_1, y_1)$ and $(x_2, y_2)$, with $x_1 < x_2$ and $y_1 < y_2$, in an $N \times N$ square, where in each column there is some interval of acceptable points. Furthermore, as the $x$-coordinate of the column increases, both endpoints of the corresponding column either decrease or stay the same.
We propose a linear scan through the possibilities for $x_2$. For each $x_2$, there is some acceptable interval $[l, r]$ for the value of $y_2$. Instead of counting the number of acceptable triples $(x_1, y_1, y_2)$, we will count the number of unacceptable triples with $x_1 < x_2$ and $y_1 < y_2$ and $l \leq y_2 \leq r$, and subtract this count from the total number of such triples.
Note that if $y_2 < l$, then $y_1 < l$, so by monotonicity of interval endpoints, $(x_1,y_1)$ is itself an unacceptable point. Therefore we can drop the condition $y_2 \geq l$ entirely.
We must compute two quantities:
1) the sum over all $(x_1, y_1)$, with $x_1 < x_2$, of the number of $y_2$ with $y_1 < y_2 \leq r$.
2) the sum over all unacceptable $(x_1, y_1)$, with $x_1 < x_2$, of the number of $y_2$ with $y_1 < y_2 \leq r$.
The first quantity can be evaluated with a simple formula. To evaluate the second quantity, we divide it into two quantities: the sum where $y_1 < l$, and the sum where $y_1 \geq l$.
If $y_1 < l$, then $(x_1, y_1)$ is an unacceptable point for all $x_1 < x_2$, so this sum again has a simple closed-form formula. We turn our attention to the case $y_1 \geq l$. For each $y$, there is some bound $\text{left}(y)$ so that $(x,y)$ is unacceptable if and only if $x \leq \text{left}(y)$. For $y_1 \geq l$, this bound is no larger than $x_2$, so the set of unacceptable $(x_1,y_1)$ with $x_1 < x_2$ is in fact independent of $x_2$. So we can precompute prefix sums of $\text{left}(y)$ and prefix sums of $y \cdot \text{left}(y)$, and during our scan, for each $x_2$, we can evaluate the case-$(y_1 \geq l)$ sum in terms of these prefix sums.
Here is an implementation of the above solution.
#include <iostream> #include <cstdlib> #include <algorithm> using namespace std; #define MAXN 100000 #define MOD 1000000007 int N; int x[MAXN], y[MAXN]; int A[MAXN]; int top[MAXN]; int lft[MAXN]; long long sumLeft[MAXN]; long long stairSumLeft[MAXN]; int main() { cin >> N; for(int i=0;i<N;i++) { cin >> x[i] >> y[i]; A[x[i]] = y[i]; } int low = N; for(int i=0;i<N;i++) while(A[i] < low) lft[--low] = i; while(low > 0) lft[--low] = N; sumLeft[N-1] = lft[N-1]; for(int j=N-2;j>=0;j--) sumLeft[j] = (sumLeft[j+1] + lft[j])%MOD; stairSumLeft[N-1] = lft[N-1]; for(int j=N-2;j>=0;j--) stairSumLeft[j] = (stairSumLeft[j+1] + ((long long)lft[j])*(N-j))%MOD; top[N-1] = A[N-1]; for(int i=N-2;i>=0;i--) top[i] = max(top[i+1],A[i]); long long ans = 0; int j = N-1; for(int i=1;i<N;i++) { while(j > 0 && lft[j-1] <= i) j--; long long bad = stairSumLeft[j] - stairSumLeft[top[i]] - (N-top[i])*(sumLeft[j] - sumLeft[top[i]]); bad = ((bad%MOD)+MOD)%MOD; long long bad2 = (top[i]*((long long)j) - (j*((long long)(j-1)))/2)%MOD; bad2 = (bad2*i)%MOD; bad = (bad + bad2)%MOD; long long tot = ((top[i]*((long long)(top[i]+1)))/2)%MOD; tot = (tot*i)%MOD; ans = ans + tot - bad; ans = ((ans%MOD)+MOD)%MOD; } cout << ans << '\n'; }