可怜的ljb（树状数组，逆序对）

Description

Ljb学长最爱出题了！只不过很可惜每次比赛，大家都能准确的避开ljb的题目，ljb欲哭无泪。这次ljb希望能有人写出自己的题目，所以他开始研究大佬们的出题顺序。

他看了一场cf的排名。一共有nn个人，编号为从1到nn的整数。

QQ图片20190213220457.png

第一行是第1小时结束时的rankrank从第1名到第nn名的同学的编号，第二行是第2小时结束时的rankrank从第1名到第nn名的同学的编号。。

Ljb学长想要知道这两个小时之间有多少对同学的排名的相对顺序交换了。

Input

第一行是T(1<=T<=10)T(1<=T<=10)表示有TT组数据。

后面每组样例的第一行一个数n(1<=n<=100000)n(1<=n<=100000)表示有nn个人。

接下来的一行有nn个数表示第一小时结束时从第1名到第nn名的同学的编号。

再接下来的一行有nn个数表示第二小时结束时从第1名到第nn名的同学的编号。

保证TT组数据nn的和不超过700000700000。

Output

每组数据输出一个整数，表示答案。

Sample Input 1

2
5
5 4 2 1 3
2 5 4 1 3
4
1 2 3 4
1 2 4 3
Sample Output 1

2
1
Hint

第一组样例解释：

有两对同学的相对顺序改变了，分别是：(5,2)，(4,2)。

因为第一轮5排在2前面，但是第二轮2排在5前面，(4,2)同理，故答案是2.

第二组样例解释：

组数据有一对同学的相对顺序改变了，分别是：(3,4)。故答案是1.

因为第一轮3排在4前面，但是第二轮4排在3前面，而且仅有这一对，故答案是1.

Source

2019年集训队选拔赛

思路：树状数组求逆序对，也可以用归并排序求逆序对。

#include <cstdio>
#include <cstring>
#include <algorithm>

#define lowbit(x) (x)&(-x)
#define ll long long

using namespace std;

const int maxn = 100000+10;
ll t[maxn],n,result;
ll hashh[maxn];

void add(ll x)
{
	while(x<=maxn)
	{
		t[x]++;
		x += lowbit(x);
	}
}

ll query(ll x)
{
	ll ans=0;
	for (;x;x-=lowbit(x))
		ans+=t[x];
	return ans;
}

int main()
{
	ll T;
	scanf("%lld",&T);
	while(T--)
	{
		result = 0;
		ll temp;
		memset(t,0,sizeof(t));
		scanf("%lld",&n);
		for(ll i=0;i<n;i++)
		{
			ll help;
			scanf("%lld",&help);
			hashh[help] = i + 1;
		}
	
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",&temp);
			ll tmp = hashh[temp];
			add(tmp);
			result += i - 1 - query(tmp - 1);
		}
		printf("%lld
",result);
	}
	return 0;
}