Rinne Loves Data Structure

代码如下：

#include<cstdio>
using namespace std;
struct node
{
    int left,right,deep;
    node(){deep=-1;}
}a[300010];
bool b[300010];
long long c;
int main()
{
    int x,n,l,r,i,j;
    bool aa;
    scanf("%d",&n);
    for(j=1;j<=n;j++)
    {
        scanf("%d",&x);
        aa=b[x]=1;
        for(i=1;i<x||i+x<=n;i++)
        {
            if(i<x&&b[x-i])
            {
                l=x-i;r=a[l].right;
                aa=0;break;
            }
            if(i+x<=n&&b[x+i])
            {
                r=x+i;l=a[r].left;
                aa=0;break;
            }
        }
        if(aa) l=0,r=300001;
        a[l].right=x,a[x].left=l;
        a[r].left=x,a[x].right=r;
        if(a[l].deep>a[r].deep) a[x].deep=a[l].deep+1;
        else a[x].deep=a[r].deep+1;
        c+=a[x].deep;
        printf("%lld\n",c);
    }
    return 0;
}