我不会写成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;
}