树状数组

思路

不难发现
对于1…2..2…1这种情况来说,先删除2比先删除1更优,也就是说有匹配就删掉肯定比先删掉一个后来的匹配要优,对于12…12先删除哪个对答案的贡献是相通的…1..2..1..2…这样先删除1是最优的,所以思路就明朗了,维护一个点到他上次出现的位置有多少还没被删除的点就好了,然后我们就可以用树状数组维护一下

洛谷还要输出方案,真毒瘤

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//By AcerMo
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) x&(-x)
using namespace std;
const int M=100500;
int n,a[M],s[M],l[M];
inline void read(int &x)
{
x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return ;
}
inline void add(int p,int x)
{
for (int i=p;i<=n;i+=lowbit(i)) s[i]+=x;
return ;
}
inline int sum(int p)
{
int su=0;
for (int i=p;i;i-=lowbit(i)) su+=s[i];
return su;
}
signed main()
{
read(n);n*=2;int ans=0;
for (int i=1;i<=n;i++) read(a[i]);
for (int i=1;i<=n;i++)
if (!l[a[i]]) add(i,1),l[a[i]]=i;
else
{
ans+=sum(i)-sum(l[a[i]]);
add(l[a[i]],-1);
}
cout<<ans<<endl;
return 0;
}