原题链接：Problem - 1579E2 - Codeforces
今天学了树状数组，好牛，一个题想了一晚上才明白呜呜
1.首先这个题要想明白，每次插入一个数的时候，如果这个数插在队列的最前面，那么对ans有贡献的就是所有小于这个数的个数；如果插在队列的最后面，那么对ans有贡献的就是所有大于这个数的个数。因此也可以想到，每次插入一个数的时候，与前面的那些数的排列顺序无关，只跟它自己插在最前面还是最后面有关，所以找到前面和后面贡献的最小值就ok了。
2.数的范围较大，可以离散化将每个数变成它们相应的序号
这里有两种方法：
（1）排序&去重
去重了之后相同的数拥有相同的序号；
（2）排序&不去重
不去重的话相同的数有相同的序号，可能会出现序号为1 1 2 4 4这样的情况，即没有3这个序号
但是其实想一下，（1）也会最后少了一些后面的序号，所以没关系，最后用c[i]树状数组都是一样的用。
3.用树状数组维护区间
求小于等于一个序号的所有个数 : for (int j = a[i]; j; j -= j & -j) res1 += c[j];
是从这个序号往前，所以 j -= j & -j
这个地方还有一个点，求所有小于a[i]的个数，是用 for (int j = a[i]; j; j -= j & -j) res1 += c[j];
求所有大于a[i]的个数，是先算出所有小于等于a[i]的个数for (int j = a[i]; j; j -= j & -j) res2 += c[j];
然后，在这个数插入之前，队列中一共有i - 1个数，所以大于a[i]的个数为i - 1 - res2。
4.a[]最后储存的是原储存的a[]数组离散化后的各个值自己的序号，对a[]循环的时候，记得每次在最后for (int j = a[i]; j <= n; j += j & -j) c[j]++;
5.树状数组的下标（序号）是从1开始的，所以：
for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
算序号的时候是减去b，相当于减去0；
6.因为有多个测试样例，记得每次归零：
for (int i = 1; i <= n; i++) c[i] = 0; （从1到n就行了，树状数组序号最大到n）
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
#define rep(i, m, n) for (int i = (m); i <= (n); ++i)
#define rrep(i, m, n) for (int i = (m); i >= (n); --i)
typedef long long ll;const int N = 200010;
int a[N], b[N], c[N];int main() {int t, n;cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];for (int i = 1; i <= n; i++) c[i] = 0;sort(b + 1, b + n + 1);for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;long long ans = 0;for (int i = 1; i <= n; i++) {int res1 = 0, res2 = 0;for (int j = a[i] - 1; j; j -= j & -j) res1 += c[j];for (int j = a[i]; j; j -= j & -j) res2 += c[j];res2 = i - 1 - res2;ans += min(res1, res2);for (int j = a[i]; j <= n; j += j & -j) c[j]++;}cout << ans << endl;}return 0;
}