本文共 1430 字，大约阅读时间需要 4 分钟。

$$WhyDidtheCowCrosstheRoadIIIG$$

题目链接： / /

题目

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

输入

第一行是$N(1\le N\le 50,000)$

输出

输出满足的对数

样例输入

432441321

样例输出

3

思路

这道题要用树状数组来做。

我们先把某个数第一次出现时叫做这个数的左端点，第二次出现时叫做右端点。

代码

#include
   
    #include
    
     using namespace std;struct node{   	int l, r;}a[100001];int n, xx, ans, ge[100001];bool cmp(node x, node y) {   	return x.l < y.l;}int get(int now) {   //得到单点值	int re = 0;	for (int i = now; i > 0; i -= i & -i)		re += ge[i];	return re;}void build(int now, int ad) {   //单点加值	for (int i = now; i <= 2 * n; i += i & -i)		ge[i] += ad;}int main() {   //	freopen("circlecross.in", "r", stdin);//	freopen("circlecross.out", "w", stdout);		scanf("%d", &n);//读入	for (int i = 1; i <= 2 * n; i++) {   		scanf("%d", &xx);//读入		if (!a[xx].l) a[xx].l = i;//第一次出现			else a[xx].r = i;//第二次	}		sort(a + 1, a + n + 1, cmp);//按第一次出现时间从小到大排序		for (int i = 1; i <= n; i++) {   		ans += get(a[i].r) - get(a[i].l - 1);//得到以这个数左右端点中的已经到过的数		build(a[i].r, 1);//把数的右端点加入树状数组	}		printf("%d", ans);//输出	//	fclose(stdin);//	fclose(stdout);		return 0;}