Description：

给定长度为 $2N$ 的序列， $1\sim N$ 各处现过 $2$ 次， $i$ 第一次出现位置记为 $a_i$ ，第二次记为 $b_i$ ，求满足 $a_i<a_j<b_i<b_j$ 的对数。

$1\leqslant n\leqslant50000$

Solution1：

把所有数对找出来，按两端点之间的距离从大到小排序，每次把左右两端点在树状数组中加一，然后把答案累加两端点之间的区间和，因为由于区间越来越小，所以两个区间要么不交，要么之前的包含之后的，要么区间相交，而只有最后一种情况会被统计，所以最后求出的就是答案。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct seq

{

	int l,r;

	seq(){l = r = -1;}

}s[MAXN >> 1];

bool cmp_len(seq a,seq b){return a.r - a.l > b.r - b.l;}

int c[MAXN];

int lowbit(int x){return x & (-x);}

void add(int p){for(int i = p;i <= n * 2;i += lowbit(i))++c[i];return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int main()

{

	scanf("%d",&n);

	int a;

	for(int i = 1;i <= n * 2;++i)

	{

		scanf("%d",&a);

		if(s[a].l == -1)s[a].l = i;

		else s[a].r = i;

	}

	sort(s + 1,s + 1 + n,cmp_len);

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		add(s[i].l);add(s[i].r);

		ans += query(s[i].r - 1) - query(s[i].l);

	}

	cout << ans << endl;

	return 0;

}

Solution2：

另一种做法是按左端点排序，然后每次统计左右端点之间的标记个数，道理类似，统计上的都是合法的。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct seq

{

	int l,r;

	seq(){l = r = -1;}

}s[MAXN >> 1];

bool cmp_l(seq a,seq b){return a.l < b.l;}

int c[MAXN];

int lowbit(int x){return x & (-x);}

void add(int p){for(int i = p;i <= n * 2;i += lowbit(i))++c[i];return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int main()

{

	scanf("%d",&n);

	int a;

	for(int i = 1;i <= n * 2;++i)

	{

		scanf("%d",&a);

		if(s[a].l == -1)s[a].l = i;

		else s[a].r = i;

	}

	sort(s + 1,s + 1 + n,cmp_l);

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		add(s[i].r);

		ans += query(s[i].r - 1) - query(s[i].l);

	}

	cout << ans << endl;

	return 0;

}