题意：有$n$个区间，把它们划分成若干段，如果一段$k$个区间的交长度$\geq2$，那么会产生$\binom k2$的贡献，最大化贡献

对每个$i$用单调栈预处理出$l_i$表示最小的$j$使得$j\cdots i$这些区间的交长度$\geq2$

设$f_i$表示前$i$个区间的答案，有$f_i=\max\limits_{j=l_i}^if_{j-1}+\binom{i-j+1}2$，直接线段树上维护凸壳已经可以做到$O(n\log n)$了，但我们有优秀线性做法

思路来源于的最后一段，orz人形自走题库yww

称$[l_i,i]$为“转移区间”

我们要说明存在一种划分$[1,n]$的方式使得每个转移区间都可以被拆成（划分出来的两个区间的后缀+前缀）

划分方法是这样的：一开始设切分点$j=0$，一遇到$l_i\gt j$就把$j$设为$i$

这样划分肯定不会有划分区间严格包含转移区间：如果包含，那么会更早切分

也不会有转移区间严格包含划分区间：因为$l_i$单调，所以会更迟切分

于是每个转移区间都被分成了划分区间的后缀+前缀，前缀可以边加入边更新答案

因为后缀能更新到的DP值都在下一个划分区间，所以在做完一整个划分区间时反着DP更新下一个划分区间的答案即可

特殊情况是转移区间就是划分区间的后缀，暴力就行

总时间复杂度$O(n)$

#include
     
      #include
      
       using namespace std;typedef long long ll;typedef double du;const ll inf=9223372036854775807ll;void fmax(ll&a,ll b){	a
       
        bool gt(t a,t b){	return a>b;}template
        
         bool lt(t a,t b){	return a
         
          
           struct mq{ int a[300010]; int q[300010],h,t; mq(){ h=1; t=0; } void push(int i){ while(h<=t&&f(a[i],a[q[t]]))t--; q[++t]=i; } void pop(int i){ if(q[h]==i)h++; } int v(){ return a[q[h]]; }};mq
           
            l;mq
            
             r;int li[300010];bool cut[300010];template
             
              struct ms{ line st[300010]; int tp; void push(line v){ while(tp>1&&f(its(v,st[tp]),its(st[tp],st[tp-1])))tp--; st[++tp]=v; } ll v(int x){ if(!tp)return-inf; while(tp>1&&f(x,its(st[tp],st[tp-1])))tp--; return st[tp].v(x); }};ms
              
               pre;ms
               
                suf;ll f[300010];line v[300010];int main(){ int n,i,j,k; scanf("%d",&n); j=1; for(i=1;i<=n;i++){ scanf("%d%d",l.a+i,r.a+i); l.push(i); r.push(i); while(r.v()-l.v()<1){ l.pop(j); r.pop(j); j++; } li[i]=j; } j=0; for(i=1;i<=n;i++){ if(li[i]>j)cut[j=li[i]]=1; } cut[n]=1; for(i=1;i<=n;i++)f[i]=-inf; j=1; for(i=1;i<=n;i++){ v[i]={-i,f[i-1]+((ll)i*i-i)/2}; if(li[i]<=j){ pre.push(v[i]); fmax(f[i],pre.v(i)); } if(cut[i]){ for(j=i;j>=li[i];j--)fmax(f[i],v[j].v(i)); f[i]+=((ll)i*i+i)/2; pre.tp=0; if(i
                
                 i;j--){ while(k>=li[j])suf.push(v[k--]); fmax(f[j],suf.v(j)); } } j=i+1; }else f[i]+=((ll)i*i+i)/2; } printf("%lld",f[n]);}