逆序对4

特别鸣谢：@亚洲卷王 AK IOI

---

思路

根据@亚洲卷王 AK IOI的“逆序对2”可知，我们可以使用离散化加树状数组解决。

但是我不会离散化怎么办（我真忘了），但是如果这题强在线怎么办。

有的兄弟有的，我们可以使用无旋 Treap 解决（旋转我不懂）。

考虑每个值 $x$，答案即为 $x$ 前面的数 $>x$ 的数的数量。灵活运用无旋 Treap 的分裂，将树分为 $\le x$ 和 $>x$ 的两棵树，答案即为右数之和。

代码

int cnt,root;
struct Node
{
	int ls,rs,key,pri,sz;
}t[1000005];
void build(int x)
{
	t[++cnt].sz=1;
	t[cnt].ls=t[cnt].rs=0;
	t[cnt].key=x;
	t[cnt].pri=rand()*rand();
}
void update(int u)
{
	t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void split(int u,int x,int& L,int& R)
{
	if(!u)
	{
		L=R=0;
		return ;
	}
	if(t[u].key<=x)
	{
		L=u;
		split(t[u].rs,x,t[u].rs,R);
	}
	else
	{
		R=u;
		split(t[u].ls,x,L,t[u].ls);
	}
	update(u);
}
int merge(int L,int R)
{
	if(L==0||R==0)return L+R;
	if(t[L].pri>t[R].pri)
	{
		t[L].rs=merge(t[L].rs,R);
		update(L);
		return L;
	}
	t[R].ls=merge(L,t[R].ls);
	update(R);
	return R;
}
void insert(int x)
{
	int L,R;
	split(root,x,L,R);
	build(x);
	int tmp=merge(L,cnt);
	root=merge(tmp,R);
}
int rk(int x)
{
	int L,R;
	split(root,x,L,R);
	int tmp=t[R].sz;
	root=merge(L,R);
	return tmp;
}
int n,i,a,sum;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a;
        sum+=rk(a);
        //cout<<rk(a)<<endl;
        insert(a);
    }
    cout<<sum;
	return 0;
}

于是我们借助无旋 Treap 的大常数抢到了最差解（$160$ 毫秒）。