原题链接
解析
首先观察到，对于一个以 \(x\) 为根的子树，左右子树内部叶子的排列顺序不会影响最终是否要在 \(x\) 点进行交换操作。也就是说，可以把求以左/右子树的答案看作是一个子问题。现在假设我们已经处理完了左右子树，接下来判断是否要交换左右子树。对于不交换的情况，贡献为 \(\sum_{x\in L}\sum_{y\in R}[x>y]\)，其中 \(L,R\) 分别为左右子树的叶子权值集合。同理可得交换情况的贡献。对于内层的求和，考虑使用权值线段树优化掉，这样左右两棵子树各有一棵权值线段树，对于外层的求和，可以在合并的时候处理，具体地：
设当前权值线段树结点为 \(p\)，管辖区间为 \([l,r]\)，左右子树对应的权值线段树分别为 \(T_l,T_r\)。
- 对于 \(T_l\) 中有，但在 \(T_r\) 中没有的结点 \(p\)，在此处统计 \(T_r\) 在 \([r + 1,n]\) 中的元素个数，将其与 \(T_l\) 在 \([l,r]\) 中的元素个数相乘。
- 对于两子树均有的满足 \(l=r\) 的结点 \(p\)，在此处统计 \(T_r\) 在 \([r + 1,n]\) 中的元素个数。
时间复杂度 \(O(n \log^2 n)\)。
然而，此题的空间限制为 64 MiB，统计时的查询操作会使得我们要开的点数乘以二从而 MLE（虽然由于洛谷的空间计算机制，使用此种做法仍然可以通过本题）。
想要抛弃查询函数，其实只需换个地方查询。对于当前权值区间 \([l,r]\)，将左半边和右半边划分为子问题，那么就只需要统计横跨左右两边的逆序对了，其数量即为 \(T_l\) 在 \([l,mid]\) 中的元素个数乘上 \(T_r\) 在 \([mid + 1,r]\) 中的元素个数。
时间复杂度 \(O(n \log n)\)。
代码
/*
*/
#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
#define mid (l + r >> 1)
using namespace std;
const int N = 2e5 + 5,M = 19;
typedef long long ll;
typedef pair<int,int> pii;
int tl[N << 2],tr[N << 2],ls[N * M],rs[N * M],rt[N << 2],cnt = 1,siz,val[N << 2];
int t[N * M];
ll res;
void read(int x,int f){int l,r;cin>>l;cnt++;tl[x] = cnt; if(!l){read(cnt,x);}else{val[cnt] = l;}cin>>r;cnt++;tr[x] = cnt;if(!r){read(cnt,x);}else{val[cnt] = r;}
}
void push_up(int p){t[p] = t[ls[p]] + t[rs[p]];
}
void add(int &p,int l,int r,int k,int x){if(l > k || r < k) return;if(!p) p = ++siz;if(l == r){t[p] += x;return;}add(ls[p],l,mid,k,x),add(rs[p],mid + 1,r,k,x);push_up(p);
}
ll c1,c2;
int merge(int &x,int &y,int l,int r){c1 += 1ll * t[ls[x]] * t[rs[y]];c2 += 1ll * t[rs[x]] * t[ls[y]];if(!x || !y){return max(x,y);}if(l == r){t[x] += t[y];return x; }ls[x] = merge(ls[x],ls[y],l,mid);rs[x] = merge(rs[x],rs[y],mid + 1,r);push_up(x);return x;
}
void sol(int x){if(!x) return;if(!tl[x]){add(rt[x],1,N - 1,val[x],1);return; }sol(tl[x]),sol(tr[x]);c1 = 0,c2 = 0;rt[x] = merge(rt[tl[x]],rt[tr[x]],1,N - 1);res += min(c1,c2);
}
int main(){ios::sync_with_stdio(false);cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n;cin>>n;int x;cin>>x;if(n == 1){cout<<0;return 0;}read(1,0);sol(1);cout<<res;return 0;
}