RT

在第是一个点的14211个数据周围出了错误

#include <bits/stdc++.h>

using namespace std;

const int N = 500000 ; 

struct T{
	int ls,rs,app;
	T(){ls=rs=app=0;}
}t[4*N+10];

int n,pos[N+10],idex,maxn,root;
long long a[N+10],b[N+10],ans;

int init()
{
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-(b+1);
	for(int i=1;i<=n;i++)
	{
		int k=lower_bound(b+1,b+1+n,a[i])-b;
		pos[i]=k; 
	}
	return len;
}

inline void updata(int x,int l,int r,int &now)
{
	if(now==0)now=++idex;
	if(l==r)
	{
		t[now].app++;
	}
	else
	{
		int mid=(l+r)>>1;
		if(x<=mid)updata(x,l,mid,t[now].ls);
		else updata(x,mid+1,r,t[now].rs);
		t[now].app=t[t[now].ls].app+t[t[now].rs].app;
	}
	return;
}

inline int query(int q,int w,int l,int r,int now)
{
	if(now==0)return 0;
	if(q<=l&&r<=w)return t[now].app;
	else
	{
		int mid=(l+r)>>1;
		int res=0;
		if(q<=mid)res+=query(q,w,l,mid,t[now].ls);
		if(w>mid)res+=query(q,w,mid+1,r,t[now].rs);
		return res; 
	}
}

int main()
{
	//freopen("P1908_11.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	maxn=init();
	for(int i=1;i<=n;i++)
	{
		updata(pos[i],1,maxn,root);
		if(pos[i]!=maxn)ans+=query(pos[i]+1,maxn,1,maxn,root);
	}
	cout<<ans<<endl;
	return 0;
}