题目传送门(BZOJ)

设两个数 ,考虑它们的可能的排列: . . 这两种情况在最优解中 之间一定不会发生 交换。发生交换的只可能是 这种,并且可以发现每次操作都会把 这种情况变成不需要交换的另两 种情况,也就是说,答案 = 所有 这种情况的个数。我们可以 枚举找一下这种情况。具体地,我们扫到 一个数,如果这个数以前没有出现过,则在数的位置上 ,否则,在这个数第一次出现的位置到当前位置开始,

求这段区间和并加到 中,然后在第一次出现的位置上

题解 :

我们拿两个数X, Y为例, 在不考虑他们中间有什么的情况下, 有两种情况一定不会发生交换, 及XXYY/XYYX,

发生交换的只能是XYXY这种. 并且每次操作都会把这种情况交换成不需要交换的另两种情况, 因为在删掉初始

这代表了答案就是\sum XYXY, 所以, 我们可以直接统计这种情况的个数.

具体操作方法 : 我们扫到一个数,若它从未出现过, 则在这个位置上加一, 否则求从上次出现的位置到这个位置的区间和, 相当于加上了这个区间所有和这个数字配成要删情况的个数 并删掉上个位置的1, 有些类似于逆序对.

如果 WA 了, 记得开long long

代码 :

// 敲简单的代码#include <cstdio>#include <cstring>using namespace std;const int N = 101000;int t[N], pos[N], n;long long ans;void add(int x, int c) {for(;x<=n;x+=x&-x)t[x]+=c;}int inq(int x) {int ret = 0; for(;x;x-=x&-x) ret += t[x]; return ret;}int main() { scanf("%d", &n); n <<= 1; for(int i = 1, x; i <= n; i ++ ) { scanf("%d", &x); if(!pos[x]) add(pos[x]=i, 1); else ans += inq(i)-inq(pos[x]), add(pos[x], -1); } printf("%lld\n", ans);}