链接：https://codeforces.com/problemset/problem/1676/H2

借鉴：https://blog.csdn.net/sigd/article/details/124717093

https://blog.csdn.net/qq_61057438/article/details/124702680

题目大意：要求在上下两个区间连线，上面按次序1....n，下面连线位置从输入得到。例如样例中

7 
4 1 4 6 7 7 5

那么连线方式就是上面1和下面4，上面2和下面1，即线段[1,4],[2,1],[3,4],[4,6],[5,7],[6,7][7,5]

首先可以观察到，上下连线，上面的一定是递增的，这样连线了 14  ，如果2要想成交点的话，就必须要求2连到4以内

这样也就是看一看下面这个数   之前有多少数是比这个数大的。
这就转换成了树状数组的模板题
类似于我做过的洛谷的小鱼比可爱问题：https://www.luogu.com.cn/problem/P1428   将所有的情况相加就是相交的交点数量

//借鉴大佬：因为上标记是依次递增的，所以我们可以从后往前考虑情况，前面的标记只要是连到了后面的标记所链接的数后面，那么就形成交点
从后往前，每次我们求和当前标记的数a[i] ，我们都令后面的数在树状数组内+1，往前标记所连接的数连到了这些数，我们可以再次进行累加
//自己做的：也很简单，就是我们考虑从当前下标的数开始，往后的数+1，这样后面的上标连接到这些数的时候可以进行累加，这样只需要在树状数组模板上更改一些条件就可以

代码：从后往前遍历

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a[2*100010], tree[2*100010];
int n;
ll lowbits(ll x)
{
	return x&(-x);
}
void update(int x) 
{
	while (x <= n) 
	{
		tree[x]++;
		x += lowbits(x);
	}
}
int getsum(int x) 
{
	ll ans = 0;
	while(x) 
	{
		ans += tree[x];
		x -= lowbits(x);
	}
	return ans;
}


int main() 
{
	int t;
	cin >> t;
	while (t--) 
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			tree[i] = 0;
		}
		ll sum = 0;
		for (int i = n; i >= 1; i--) 
		{
			sum += getsum(a[i]); 
			update(a[i]);
		}
		cout << sum << endl;
	}
	return 0;
}

代码：从前往后遍历

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a[2*100010], tree[2*100010];
int n;
//模板 
ll lowbits(ll x)
{
	return x&(-x);
}
void update(ll x) 
{
	while (x >=1) //之后链接的数  大于 x的 都+1 ，因为之后链接的上标记一定小于 i  
	{
		tree[x]++;
		x -= lowbits(x);
	}
}
int getsum(int x) 
{
	ll ans = 0;
	while(x<=n) 
	{
		ans += tree[x];
		x += lowbits(x);
	}
	return ans;
}
//

int main() 
{
	int t;
	cin >> t;
	while (t--) 
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			tree[i] = 0;
		}
		ll sum = 0;
		for (int i = 1; i <= n; i++) 
		{
			sum += getsum(a[i]); 
			update(a[i]);
		}
		cout << sum << endl;
	}
	return 0;
}