这道题平衡树为什么会WA

RT.

FHQ Treap做的，思路是每次添加一个元素的时候查询此时的排名，然后用当前元素个数减去排名累加到ans上。

求大佬解答qwq.

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,a,root,idx,ran;
struct node
{
    int l,r,val,key,size;
}tr[500005];
void pushup(int x)
{
    tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+1;
}
void split(int p,int v,int &x,int &y)
{
    if(!p)
    {
        x=y=0ll;
        return;
    }
    if(tr[p].val<=v)
    {
        x=p;
        split(tr[x].r,v,tr[x].r,y);
    }
    else
    {
        y=p;
        split(tr[y].l,v,x,tr[y].l);
    }
    pushup(p);
}
int merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(tr[x].key<tr[y].key)
    {
        tr[x].r=merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else
    {
        tr[y].l=merge(x,tr[y].l);
        pushup(y);
        return y;
    }
}
int newnode(int v)
{
    tr[++idx].val=v;
    tr[idx].key=rand();
    tr[idx].size=1;
    return idx;
}
void insert(int v)
{
    int x,y,z;
    split(root,v,x,y);
    z=newnode(v);
    root=merge(merge(x,z),y);
}
void getrank(int v)
{
    int x,y;
    split(root,v-1,x,y);
    ran=tr[x].size+1;
    root=merge(x,y);
}
signed main()
{
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        insert(a);
        getrank(a);
        if(i!=1)
            ans+=(i-ran);
    }
    cout<<ans;
    return 0;
}