这道题咋看都是无法从dp入手，那么就从数据结构入手！；
首先你要会权值线段树和线段树合并。
然后你要知道：
对于任意一个节点，交换左右子树对当前节点和前面的所有节点没有影响。
因为这是前序遍历：根节点->左子树->右子树。可以看到，交换左右子树对前面的节点无影响。
我们清楚，交换子树只会对该逆序对横跨左右子树这种情况产生影响。因此，我们只需要在合并线段树的过程中统计交换子树的逆序对个数ans1和不交换子树的逆序对个数ans1，取 min(ans1,ans2) 累加到答案中就行了。
每一次合并线段树时，递归到除了叶节点的所有节点，都要累加逆序对个数u,v。
需要注意，我们能够这样计算是因为无论左右儿子怎么交换，影响的都只有当前部分的逆序对个数，而不会影响深度更浅的节点的值。
注意要回收内存，否则会MLE
#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n;
class node{
public:
long long lson,rson,sum;
}tree[200010*13];
long long ans1,ans2;
int now=0;
int merge(int x,int y,int l,int r){
if(!x) return y;
if(!y) return x;
if(l==r){
tree[x].sum+=tree[y].sum;
return x;
}
ans1+=tree[tree[x].rson].sum*tree[tree[y].lson].sum;
ans2+=tree[tree[x].lson].sum*tree[tree[y].rson].sum;
int mid=(l+r)>>1;
tree[x].lson=merge(tree[x].lson,tree[y].lson,l,mid);
tree[x].rson=merge(tree[x].rson,tree[y].rson,mid+1,r);
tree[x].sum=(tree[tree[x].lson].sum+tree[tree[x].rson].sum);
return x;
}
int build(int l,int r,int goal){
int pos=++now;
tree[pos].sum++;
if(l==r) return pos;
int mid=(l+r)>>1;
if(goal<=mid){
tree[pos].lson=build(l,mid,goal);
}
else{
tree[pos].rson=build(mid+1,r,goal);
}
return pos;
}
long long ans=0;
int read()
{
int pos,v;
scanf("%d",&v);
if(v==0){
int lson=read(),rson=read();
ans1=0; ans2=0;
pos=merge(lson,rson,1,n);
ans+=min(ans1,ans2);
}
else{
return pos=build(1,n,v);
}
return pos;
}
int main()
{
scanf("%d",&n);
read();
cout<<ans;
}