权值线段树TLE25

我不会写成O(n^2)了吧

#include <bits/stdc++.h>
using namespace std;
int n,id[1000009],cnt,ans;
pair<int,int> f[1000009];
struct node
{
    int l,r,d;
}a[4000009];
void build(int d,int l,int r)
{
    a[d].l=l;
    a[d].r=r;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(d<<1,l,mid);
    build(d<<1|1,mid+1,r);
}
void add(int d,int x)
{
    if(a[d].l==a[d].r) 
    {
        if(a[d].l==x) a[d].d=(a[d].d|1);
        return ;
    }
    add(d<<1,x);
    add(d<<1|1,x);
    a[d].d=a[d<<1].d+a[d<<1|1].d;
}
int ask(int d,int l,int r)
{
    int res=0;
    if(a[d].l>r||a[d].r<l) return 0;
    if(a[d].r<=r&&a[d].l>=l) return a[d].d;
    res+=ask(d<<1,l,r);
    res+=ask(d<<1|1,l,r);
    return res;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i].first;
        f[i].second=i;
    }
    sort(f+1,f+n+1);
    for(int i=1;i<=n;i++)
    {
        if(f[i].first!=f[i-1].first) cnt++;
        id[f[i].second]=cnt;
    }
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        add(1,id[i]);
        ans+=ask(1,id[i]+1,cnt);
    }
    cout<<ans<<endl;
    return 0;
}