题目描述

略

样例

略

算法1

SPLay $O(nlogn)$

splay的查询排名可以用来计算区间小于某个数的个数
那不就很好吗（

时间复杂度

常数略大，但是可以卡过去

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
class Splay 
{
    static int const N=200010;
    public:
    int rt, tot,fa[N],ch[N][2],cnt[N], sz[N];
    int val[N];
    int l[N],r[N];
    inline void init()
    {
        rt=tot=0;
    }
    inline void pushup(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }//更新节点x的sz 
    inline bool get(int x) { return x == ch[fa[x]][1]; }//x是否是其父亲节点的右儿子 
    inline void clear(int x) {ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;}//删除节点x 
    inline void rotate(int x,int &k)
    {
        int y=fa[x],z=fa[y],d=ch[y][1]==x;
        if (y==k)k=x;//k是x的父亲节点 
        else ch[z][ch[z][1]==y]=x;
        fa[ch[x][d^1]]=y;fa[y]=x;fa[x]=z;
        ch[y][d]=ch[x][d^1];ch[x][d^1]=y;
        pushup(x);pushup(y);
    }
    inline void splay(int x,int &k)//把节点x与节点k互换，随时更新k的值，防止把k旋转到x子树里 
    {
        while (x!=k)
        {
            int y=fa[x],z=fa[y];
            if (y!=k)//双旋操作 
            {
                if ((ch[z][0]==y)^(ch[y][0]==x))rotate(x,k);
                else rotate(y,k);
            }
            rotate(x,k);
        }
    }
    int find(int x) //查找数x，用于迭代器使用 
    {
        int res = 0, now = rt;
        while (now) 
        {
            if (x<val[now]) now=ch[now][0];
            else 
            { 
                if (x==val[now]) 
                {
                    splay(now,rt);
                    return now;
                }
                now=ch[now][1];
            }
        }
        return 0;
    }
    int pre() //查询根节点的前驱，小于根节点权值，且最大的数 
    {
        int now = ch[rt][0];
        while (ch[now][1]) now = ch[now][1];
        return now;
    }
    int nxt()//查询根节点的后继，大于根节点权值，且最小的数 
    {
        int now = ch[rt][1];
        while (ch[now][0]) now = ch[now][0];
        return now;
    }
    int ins(int x) //插入一个数x 
    {
        if (!rt) 
        {
            val[++tot] = x;cnt[tot]++;
            rt = tot;pushup(rt);//新建一个节点(此时树为空)
            return tot;
        }
        int now = rt, f = 0;//now：当前查询到的节点 ，f：cnr的父亲节点 
        while (1) 
        {
            if (val[now] == x) 
            {
                cnt[now]++;
                pushup(now);pushup(f);
                splay(now,rt);
                break;
            }
            f=now;
            now=ch[now][val[now]<x];//根据BST的性质往下查询 
            if (!now)//如果平衡树中不存在权值为k的节点，则新建一个节点 
            {
                val[++tot]=x;cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < x] = tot;
                pushup(tot);pushup(f);
                splay(tot,rt);//每次操作都要splay，保证均摊复杂度能做到logn级别 
                now=tot;
                break;
            }
        }
        int p=pre();
        int t=nxt();
        r[p]=l[t]=now;
        r[now]=t;l[now]=p;
        return now;
    }
    int rk(int x) //查询数x的排名(从小到大),只要查到权值等于x的节点，所有小于x的数都在x左子树上。 
    {
        int res = 0, now = rt;//小于x的数有res个
        while (1) 
        {
            if (x < val[now]) now = ch[now][0];//根据BST的性质往下找到x所在的位置 
            else 
            {
                res += sz[ch[now][0]];//往右走的时候先累加左子树的数量 
                if (x == val[now]) 
                {
                    splay(now,rt);
                    return res + 1;
                }
                res += cnt[now];
                now = ch[now][1];
            }
        }
    }
    int kth(int k) //查询第k大的数的权值 
    {
        int now = rt;
        while (1) 
        {
            if (ch[now][0] && k <= sz[ch[now][0]]) 
                now = ch[now][0];
            else 
            {
                k -= cnt[now] + sz[ch[now][0]];
                if (k <= 0) 
                {
                  splay(now,rt);
                  return val[now];
                }
                now = ch[now][1];
            }
        }
    }
    //注意！执行前驱后继时要先插入x节点(插入时会自动把他旋转到根节点)，然后进行处理，最后再删除x节点。保证每次处理都在根节点进行处理 
    int del(int k) //删除k节点 
    {
        if(!find(k)) return 0;
        rk(k);      
        int p=pre();
        int t=nxt();
        r[l[k]]=r[k];
        l[r[k]]=l[k];  //这一步的目的是把k旋转到根节点，方便后续处理以及复杂度保证(每一步操作尽量在根节点进行，即用双旋操作缩短深度在处理，防止退化)
        if (cnt[rt] > 1) 
        {
            cnt[rt]--;
            pushup(rt);
            return 1;
        }
        if (!ch[rt][0] && !ch[rt][1])//树只剩根节点时，树变为空 
        {
            clear(rt);
            rt = 0;
            return 1;
        }
        if (!ch[rt][0]) //如果左子树为空，则以右子树为根 
        {
            int now = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(now);
            return 1;
        }
        if (!ch[rt][1])//如果右子树为空，则以左子树为根 
        {
            int now = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(now);
            return 1;
        }
        //左右子树均不为空，则以左子树最大权值 的节点做为根节点 (维持BST的性质)
        int now = rt;
        int x = pre();
        splay(x,rt);
        fa[ch[now][1]] = x;//把x旋转到根节点后，原来根节点的右儿子还未接到x节点 
        ch[x][1] = ch[now][1];
        clear(now);//删除原来的根节点 
        pushup(rt);
    }
    void build(int l,int r,int &rt)//建树，根据初始序列id建 ，默认初始1，2，3，4，5 
    {
        if (l>r) return;
        int mid=(l+r)>>1;
        if (mid<rt)ch[rt][0]=mid;
        else ch[rt][1]=mid;
        fa[mid]=rt;sz[mid]=cnt[mid]=1;
        if (l==r)return;
        build(l,mid-1,mid);build(mid+1,r,mid);
        pushup(mid);
    }
} s1,s2;
int a[200020],l[200020],r[200020],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    {   
        s1.ins(a[i]);
        s2.ins(a[n-i+1]);
        l[i]=1ll*s1.rk(a[i])-1;
        r[n-i+1]=1ll*s2.rk(a[n-i+1])-1;
    }
//  for(int i=1;i<=n;i++) cout<<l[i]<<' ';
//  cout<<endl;
//  for(int i=1;i<=n;i++) cout<<r[i]<<' ';
//  cout<<endl;
    long long ans=0;        
    for(int i=1;i<=n;i++)
    {
        ans+=1ll*(i-1-l[i])*(n-i-r[i]);
    }
    cout<<ans<<' ';
    ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=1ll*l[i]*r[i];
    }
    cout<<ans;
}