link

蒟蒻太菜，只会 $\mathcal O(n \log n)$ 解法。

想问一下下面这个 $\mathcal O(n)$ 代码的原理是什么。

#include<bits/stdc++.h>
using namespace std;
int n,f[100009],a,b,mx;
long long ans;
int main(){
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        f[a]=max(f[a],2*b-2*a-1);
        mx=max(b,mx);
    }
    for(int i=1;i<=mx;i++){
        f[i]=max(f[i-1]-2,f[i]);
        ans+=f[i];
    }
    printf("%lld\n",ans);
    return 0;
}