挺好的一道优化题，重点是这个序列其实是由一堆操作添加的数字串的后缀串组成的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,inf=1e18;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct node{int l,r,mx;}tr[2][N<<2];
void pushup(int id,int p){tr[id][p].mx=max(tr[id][lc(p)].mx,tr[id][rc(p)].mx);}
void bt(int id,int p,int l,int r)
{
	tr[id][p]={l,r,-inf};
	if(l==r)return ;
	int mid=(l+r)>>1;
	bt(id,lc(p),l,mid);bt(id,rc(p),mid+1,r);
	pushup(id,p);
}
void change(int id,int p,int x,int k)
{
	if(tr[id][p].l>x||tr[id][p].r<x)return ;
	if(tr[id][p].l==tr[id][p].r)
	{
		tr[id][p].mx=max(tr[id][p].mx,k);
		return;
	}
	change(id,lc(p),x,k);change(id,rc(p),x,k);
	pushup(id,p);
}
int query(int id,int p,int l,int r)
{
	if(tr[id][p].l>r||tr[id][p].r<l)return -inf;
	if(l<=tr[id][p].l&&tr[id][p].r<=r)return tr[id][p].mx;
	return max(query(id,lc(p),l,r),query(id,rc(p),l,r));
}
int b[N],blen,l[N],r[N],dp[N];map<int,int>mp;
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];
		b[++blen]=l[i];b[++blen]=r[i];b[++blen]=l[i]-1;
	}
	sort(b+1,b+blen+1);int k=unique(b+1,b+blen+1)-b-1;
	for(int i=1;i<=k;i++)mp[b[i]]=i;
	bt(0,1,1,blen);bt(1,1,1,blen);
	for(int i=1;i<=n;i++)
	{
		int sum1=query(0,1,1,mp[l[i]-1]),sum2=query(1,1,mp[l[i]],blen);
		dp[i]=max({sum1,sum2+l[i]-1,0ll})+r[i]-l[i]+1;
		change(0,1,mp[r[i]],dp[i]);change(1,1,mp[r[i]],dp[i]-r[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}