未写完

code:

#include <map>
#include <string>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 300007
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll ans;
int rt[N<<1],ar[N],del[N],n,st,ed,length;
namespace seg
{
    int tot;
    struct node { int l,r,sum; }s[N*50];
    void update(int &x,int l,int r,int p,int v)
    {
        if(!x) x=++tot;
        ++s[x].sum;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(p<=mid) update(s[x].l,l,mid,p,v);
        else update(s[x].r,mid+1,r,p,v);
    }
    int query(int x,int l,int r,int L,int R)
    {
        if(l>=L&&r<=R) return s[x].sum;
        int mid=(l+r)>>1,re=0;
        if(L<=mid) re+=query(s[x].l,l,mid,L,R);
        if(R>mid)  re+=query(s[x].r,mid+1,r,L,R);
        return re;
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        int now=++tot;
        s[now].sum=s[x].sum+s[y].sum;
        s[now].l=merge(s[x].l,s[y].l);
        s[now].r=merge(s[x].r,s[y].r);
        return now;
    }
    ll queryr(int x,int l,int r,int L,int R)
    {
        if(!x||L>R) return 0;
        if(l>=L&&r<=R) return (ll)s[x].sum*max(0,min(l-st+1,length));
        int mid=(l+r)>>1;  ll re=0ll;
        if(L<=mid)  re+=queryr(s[x].l,l,mid,L,R);
        if(R>mid)   re+=queryr(s[x].r,mid+1,r,L,R);
        return re;
    }
    ll queryl(int x,int l,int r,int L,int R)
    {
        if(!x||L>R) return 0;
        if(l>=L&&r<=R) return (ll)s[x].sum*max(0,min(ed-r+1,length));
        int mid=(l+r)>>1;  ll re=0ll;
        if(L<=mid)  re+=queryl(s[x].l,l,mid,L,R);
        if(R>mid)   re+=queryl(s[x].r,mid+1,r,L,R);
        return re;
    }
};
namespace sam
{
    int last,tot;
    map<int,int>ch[N<<1];
    int mx[N<<1],pre[N<<1],A[N<<1],rk[N<<1],pos[N<<1];
    void init() { last=tot=1; }
    struct node
    {
        int x,id;
        node(int x=0,int id=0):x(x),id(id){}
    };
    vector<node>G[N<<1];
    void extend(int c,int i)
    {
        int np=++tot,p=last;
        mx[np]=mx[p]+1,last=np;
        for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;
        if(!p) pre[np]=1;
        else
        {
            int q=ch[p][c];
            if(mx[q]==mx[p]+1) pre[np]=q;
            else
            {
                int nq=++tot;
                mx[nq]=mx[p]+1;
                ch[nq]=ch[q];
                pre[nq]=pre[q],pre[q]=pre[np]=nq;
                for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
            }
        }
        seg::update(rt[np],1,n,i,1);
        G[np].push_back(node(i,rt[np]));
    }
    void solve()
    {
        int i,j;
        for(i=1;i<=tot;++i) ++A[mx[i]],pos[i]=i;
        for(i=1;i<=tot;++i) A[i]+=A[i-1];
        for(i=1;i<=tot;++i) rk[A[mx[i]]--]=i;
        for(i=tot;i>1;--i)
        {
            int u=rk[i];
            int ff=pre[u];
            if(ff==1) continue;
            int rt1=rt[u],rt2=rt[ff];
            if(G[pos[u]].size()>G[pos[ff]].size()) swap(pos[u],pos[ff]),swap(rt1,rt2);
            printf("1 :: ");
            for(j=0;j<G[pos[ff]].size();++j)  printf(" %d",G[pos[ff]][j]);
            printf("\n");
            printf("2 :: ");
            for(j=0;j<G[pos[u]].size();++j)
            {
                printf(" %d",G[pos[u]][j]);
                node e=G[pos[u]][j];
                length=mx[ff];
                st=e.x+1;
                ed=e.x-1;
                ll tp=ans;
                ans+=seg::queryr(rt2,1,n,st,n);
                ans+=seg::queryl(rt2,1,n,1,ed);
                G[pos[ff]].push_back(G[pos[u]][j]);
            }
            printf("\n");
            rt[ff]=seg::merge(rt[ff],rt[u]);
        }
    }
};
int main()
{
    int i,j;
    setIO("input");
    sam::init(),scanf("%d",&n),ans=(ll)n*(n-1)/2;
    for(i=1;i<=n;++i) scanf("%d",&ar[i]);
    for(i=1;i<n;++i)  del[i]=ar[i+1]-ar[i];
    --n;
    for(i=1;i<=n;++i) sam::extend(del[i],i);
    sam::solve();
    printf("%lld\n",ans);
    return 0;
}