题意：
长度为1e91e9的(1,−1)(1,−1)序列，下标从00到1e9−11e9−1，已知有nn个区间为11，其他为−1−1， 问存在多少个区间的和>1>1（保证∑1≤i≤nr[i]−l[i]+1≤1e7∑1≤i≤nr[i]−l[i]+1≤1e7）.
给你一个n 表示有n段连续的1序列 现在问你 在总长度为0~1e9-1的范围内有多少个大于0的子段.
题解
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
const int M = 4e7 + 10;
typedef long long ll;
int l[N], r[N], L[N], R[N];
ll num[M];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
}
l[0] = r[0] = L[0] = R[0] = -1, l[n + 1] = r[n + 1] = 1e9;
int len = 0;
for (int i = 1; i <= n; i++) {
len += r[i] - l[i] + 1;
R[i] = min(r[i] + len, l[i + 1] - 1);
len -= l[i + 1] - r[i] - 1;
if (len < 0)
len = 0;
}
len = 0;
for (int i = n; i >= 1; i--) {
len += r[i] - l[i] + 1;
L[i] = max(l[i] - len, r[i - 1] + 1);
len -= l[i] - r[i - 1] - 1;
if (len < 0)
len = 0;
}
int now = 2e7 + 10;
ll sum = 0;
num[now] = 1;
ll ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = max(L[i], R[i - 1] + 1); j <= R[i]; j++) {
if (j >= l[i] && j <= r[i]) {
sum += num[now];
num[++now]++;
} else {
sum -= num[--now];
num[now]++;
}
ans += sum;
}
}
cout << ans << endl;
return 0;
}
参考博客：
https://blog.csdn.net/qq_40791842/article/details/96736137
https://blog.csdn.net/qq_40871466/article/details/97104326
https://blog.csdn.net/toohandsomeieaseid/article/details/98848517
https://www.cnblogs.com/Yinku/p/11221494.html
https://www.cnblogs.com/wmj6/p/11288038.html
原文：https://www.cnblogs.com/young-children/p/11354350.html