原题：[洛谷P9310]([P9310 EGOI2021] Luna likes Love / 卢娜爱磕 cp - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
题目大意
给定一个长度为 \(\large 2n(n\leq 10^5)\) 的序列，序列中 \(\large 1\sim n\) 的每一个数都恰好出现两次。
可进行两种操作：
- 交换两个相邻的数的位置。
- 若两个相邻的数相同，则删去这两个数。
问最少进行多少次操作可使序列为空。
思路
显然对于序列中一个在前面出现过的数 \(\large a_i\)，我们应该把它交换到与它上一次出现的位置 \(\large lst_{a_i}\) 相邻，并删掉它们，那么代价就是 它们之间剩余的数的数量 \(\large +1\)。
暴力的话，用 \(\large vis_i\) 标记第 \(\large i\) 个数是否已被删去。如果 \(\large a_i\) 在前面出现过，那么让 \(\large ans\) 加上 \(\large\sum\limits_{j=lst_{a_i}}^ivis_j+1\)，然后让 \(\large vis_i=vis_{lst_{a_i}}=1\)。
考虑优化。我们可以开一个前缀和数组 \(\large sum_i\)，表示前 \(\large i\) 个数里被删去的数的个数。带修，所以用树状数组。那么上面的操作可以变为：让 \(\large ans\) 加上 \(\large i-lst_{a_i}-1+1-sum_i+sum_{lst_{a_i}}\)，并 \(\large \operatorname{add}(i,1),\operatorname{add}(lst_{a_i},1)\)。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define reg register
#define int long long
using namespace std;
inline int read()
{
short f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,a,ans,c[1000010],lst[500010];
inline void add(int x) {for(;x<=2*n;x+=x&-x) c[x]=-~c[x];}
inline int ask(int x) {int ans=0; for(;x;x-=x&-x) ans+=c[x]; return ans;}
signed main()
{
n=read();
for(reg int i=1;i<=2*n;i=-~i)
{
a=read();
if(lst[a])
ans+=i-lst[a]-ask(i)+ask(lst[a]),add(lst[a]),add(i);
lst[a]=i;
}
return printf("%lld",ans),0;
}