自动搬运

查看原文

来自洛谷，原作者为

	苟全性命 **

搬运于2025-08-24 21:51:20，当前版本为作者最后更新于2018-10-03 22:44:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}