前言
这题我前前后后看了三遍，每次都是把网上相关的博客和通过代码认真看了再思考，然并卵，最后终于第三遍也就是现在终于看懂了，其实懂了之后发现其实没有那么难，但是的的确确需要思维。(博客分析那块写的啰里吧嗦又改了很多废话)
题意
在一个长度为$10^{9}$的序列上，保证只有$n(n<10^{6})$个区间等于$1$，且$1$的个数小于10^{7}，其他位置全部为$-1$，求区间和$>0$的区间数量
分析
题目意思很简单，对不对~ 那接下来我们就思考下该怎么做这题。
考虑做前缀和，问题就转化成$sum[i]-sum[j] > 0$的对数
举个栗子，比如序列$\left \{ -1,-1,-1,1,1,1,1 \right \}$，对应的前缀和为$\left \{ -1,-2,-3,-2,-1,0,1 \right \}$
那么$-1>-2$，中间的$\left \{ -1,-1,1,1,1 \right \}$区间和$>0$
由于数据范围较大不可能对整个数组前缀和进行处理，我们注意到能被1覆盖的区间长度最多有$3e7$， 因为区间向前，向后最多可以覆盖$1e7$，所以加起来就是$3e7$，这是本题求解的关键。
所以我们可以处理一下区间，让它尽可能的延伸而又不至于小于$0$，之后我们只需要计算在当前点有多少前面点的前缀和小于它就行了。这样我们就可以用树状数组来求，可范围太大了我们只能用别的方法(不甘心的我用树状数组试了下果然超时)
Code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e7+;
int l[maxn], r[maxn], n;
int L[maxn],R[maxn];
int num[maxn*];
int main()
{
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d%d", &l[i], &r[i]);
r[] = R[] = -, l[n+] = 1e9;
int len=;
for(int i = ; i <= n; i++){
len += r[i]-l[i]+;
R[i] = min(r[i]+len,l[i+]-);
len -= l[i+]-r[i]-;
if(len<) len=;
}
len=;
for(int i = n; i > ; i--){
len += r[i]-l[i]+;
L[i] = max(l[i]-len,r[i-]+);
len -= l[i]-r[i-]-;
if(len<) len=;
} int now = 1e7+;
num[now] = ;
ll sum = , ans = ;
for(int i = ; i <= n; i++){
for(int j = max(L[i],R[i-]+); j <= R[i]; j++){
if(j>=l[i]&&j<=r[i]){
sum += num[now];
num[++now]++;
}else{
sum -= num[--now];
num[now]++;
}
ans += sum;
}
}
printf("%lld",ans);
return ;
} /*
now记录的是当前的前缀和，sum记录前缀和小于now的数量，num数组记录的所有前缀和对应的数目。
假如j对应的数字是1，num[++now]显然应该加1，由于此时前缀和比上次要大，那么执行这一步操作前我们应该先把sum加上num[now]；
假如j对应的数字是-1，num[--now]也当然加1，这时候前缀和比上次要小，执行完这步后sum应当减去此时和now相等的前缀和数量就得到比now小的前缀和数量。
*/
可能有的人会跟我有一样的疑惑，一但中间出现“断层”怎么办？也即是中间有非常多的$-1$导致相邻两端不能相连。你仔细想想，其实对于我们这种做法没有任何影响，我们只处理对答案有贡献的区间的点。你可能会说如果”断层“的话前缀和应该重新计算，但是实际上我们是在判断$sum[i]-sum[j] > 0$即$sum[i]>sum[j]$，从不从$0$开始算我们并不关心，我们只在乎他们的相对大小，这里一定要好好想一想！！！
参考资料：
https://www.cnblogs.com/ckxkexing/p/11219612.html