记录编号	39353	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.077 s
提交时间	2012-07-09 15:13:09	内存使用	2.00 MiB

#include <cstdio>
#include <cstdlib>
 
#define I_F "queueb.in"
#define O_F "queueb.out"
 
const long MAXn=50000;
 
struct treap
{
    long x,y,z;
    treap *f, *l, *r;
};
 
treap pool[MAXn];
treap *ph=pool;
long n;
long s[MAXn];
long a[MAXn], b[MAXn];
long long ans=0;
treap *root=NULL;
 
void Input();
inline void Lefturn(treap*);
inline void Righturn(treap*);
long Insert(const long&);
inline void Clear();
void Search();
void Output();
 
int main()
{
    Input();
    Search();
    Output();
    return 0;
}
 
void Input()
{
    freopen(I_F,"r",stdin);
    scanf("%ld",&n);
    for (long i=0; i<n; ++i)
        scanf("%ld",&s[i]);
}
 
inline void Lefturn(treap *p)
{
    treap *f=p->f;
    treap *a=p->l, *b=p->r, *c=f->r;
    if (f->f==NULL)
        root=p;
    else
        if (f->f->l==f)
            f->f->l=p;
        else
            f->f->r=p;
    p->f=f->f;
    f->f=p;
    p->r=f;
    f->l=b;
    if (b!=NULL)
        b->f=f;
    f->z=1+((b!=NULL)?b->z:0)+((c!=NULL)?c->z:0);
    p->z=1+((a!=NULL)?a->z:0)+f->z;
}
 
inline void Righturn(treap *f)
{
    treap *p=f->f;
    treap *a=p->l, *b=f->l, *c=f->r;
    if (p->f==NULL)
        root=f;
    else
        if (p->f->l==p)
            p->f->l=f;
        else
            p->f->r=f;
    f->f=p->f;
    p->f=f;
    f->l=p;
    p->r=b;
    if (b!=NULL)
        b->f=p;
    p->z=1+((a!=NULL)?a->z:0)+((b!=NULL)?b->z:0);
    f->z=1+((c!=NULL)?c->z:0)+p->z;
}
 
long Insert(const long &x)
{
    if (root==NULL)
    {
        root=ph++;
        root->x=s[x];
        root->y=rand()%MAXn;
        root->z=1;
        root->f=root->l=root->r=NULL;
        return 0;
    }
    treap *i=root;
    while (true)
        if (s[x]==i->x)
        {
            for (treap *j=i; j!=NULL; j=j->f)
                ++j->z;
            break;
        }
        else
            if (s[x]<i->x)
                if (i->l!=NULL)
                    i=i->l;
                else
                {
                    i->l=ph++;
                    i->l->f=i;
                    i=i->l;
                    i->l=i->r=NULL;
                    i->x=s[x];
                    i->y=rand()%MAXn;
                    i->z=1;
                    for (treap *j=i->f; j!=NULL; j=j->f)
                        ++j->z;
                    break;
                }
            else
                if (i->r!=NULL)
                    i=i->r;
                else
                {
                    i->r=ph++;
                    i->r->f=i;
                    i=i->r;
                    i->l=i->r=NULL;
                    i->x=s[x];
                    i->y=rand()%MAXn;
                    i->z=1;
                    for (treap *j=i->f; j!=NULL; j=j->f)
                        ++j->z;
                    break;
                }
    while (i->f!=NULL && i->z>i->f->z)
        if (i==i->f->l)
            Lefturn(i);
        else
            Righturn(i);
    long re=(i->l!=NULL)?i->l->z:0;
    while (i->f!=NULL)
    {
        if (i==i->f->r)
            re+=(i->f->z-i->z);
        i=i->f;
    }
    return re;
}
 
inline void Clear()
{
    root=NULL;
    ph=pool;
}
 
void Search()
{
    for (long i=0; i<n; ++i)
        a[i]=Insert(i);
    Clear();
    for (long i=n-1; i>=0; --i)
        b[i]=Insert(i);
    for (long i=0; i<n; ++i)
        ans+=a[i]*b[i];
}
 
void Output()
{
    freopen(O_F,"w",stdout);
    printf("%lld\n",ans);
}