二叉树可以维护逆序对吗？
题目描述
我们都知道一颗二叉树，有前序、中序、后续三种遍历方式。
其中给定前序和中序，便可以推导出二叉树的后序。
现在给定一颗二叉树的前序和中序遍历，需要你求出二叉树的后序遍历中逆序对的数量。
逆序对： 对于一个包含 \(N\) 个非负整数的数组 \(A[1..n]\)，如果有 \(i < j\)，且 \(A[i]>A[j]\)，则称\((A[i] ,A[j])\)为数组A中的一个逆序对。
其中 \(A[i]\)为第 \(i\) 个遍历到的节点编号。
输入格式
第一行输入一个整数\(n\)，表示二叉树节点的个数。节点编号为(\(1,2,...,n\))。
第二行有 \(n\) 个整数，表示二叉树的前序遍历。
第三行有 \(n\) 个整数，表示二叉树的中序遍历。
输出格式
输出两行
第一行输出 \(n\) 个数，表示二叉树的后序遍历，每个数用一个空格分开。
第二行输出一个整数 \(k\)，表示二叉树后序遍历的逆序对数量，答案可能会爆 \(int\)。
数据范围
- \(1\le n\le 10^5\)
输入样例1
1 2 3 | |
输出样例1
1 2 | |
输入样例2
1 2 3 | |
输出样例2
1 2 | |