LGP9310 [EGTS 2021] Luna likes Love 学习笔记
Luogu Link
题意简述
有一个长为 \(2n\) 的序列 \(A\)。\(1\sim n\) 的每一个整数都在其中恰好出现两次。
可以以任意顺序任意次执行两种操作：
- 交换 \(a_i,a_{i+1}\)。
- 从序列里消掉 \((a_i,a_{i+1})\)，前提是 \(a_i=a_{i+1}\)。
问最少操作次数。
\(n\le 5\times 10^5\)。
做法解析
观察阳历。首先消去的次数显然是 \(n\) 次，所以答案就是 \(n\) 加上交换次数。
我们暂时记 \(p_1\) 为靠前出现的值为 \(p\) 的元素，\(p_2\) 为靠后出现的那个。你发现如果有 \(p_1<q_1<q_2<p_2\)，那你显然是先等 \(q\) 被消掉。这说明什么呢？举个例子，两个 \(1\) 里面夹了两个 \(2\)、两个 \(3\)、一个 \(4\)、一个 \(5\)、一个 \(6\)，那你显然是让这个 \(4\)、\(5\)、\(6\) 最终居于 \([1_1,1_2]\) 外面。
所以交换次数就是对于每一对 \(p\)，它们中间夹的不成对的元素的数量之和？不对。你考虑 \(A=\{1,2,1,2\}\)。显然交换一次即可，但是你统计出来是要两次。错的地方在于，把那对 \(1\) 里的 \(2\) 换出来之后，\(2\) 里面就没夹着 \(1\) 了（实际上就是说，因为 \(p_1,p_2\) 每夹一个 \(q_1\)，就会有 \(q_1,q_2\) 夹一个 \(p_2\)，所以刚好多算了一倍）。所以正确的总交换次数是：“它们中间夹的、不成对的、第一次出现的元素的数量”之和。
代码实现
树状数组即可。
（不能连树状数组都不用。考虑 \(1,2,3,4,3,4,1,2\)。你也不希望你在考虑 \(4\) 夹了什么的时候把 \(2\) 算进去了吧。）
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=5e5+5;
int N,A[MaxN<<1],pos[MaxN];lolo ans;
struct BinidTree{int n,t[MaxN<<1];void init(int x){n=x,fill(t,t+n+1,0);}int lowbit(int x){return x&(-x);}void add(int p,int x){for(;p<=n;p+=lowbit(p))t[p]+=x;}int gts(int p){int res=0;for(;p;res+=t[p],p-=lowbit(p));return res;}int getsum(int l,int r){return gts(r)-gts(l-1);}
}BiT;
int main(){readi(N);ans=N;BiT.init(N<<1);for(int i=1;i<=N*2;i++)readi(A[i]);for(int i=1;i<=N*2;i++){if(!pos[A[i]]){pos[A[i]]=i,BiT.add(i,1);continue;}BiT.add(pos[A[i]],-1),ans+=BiT.getsum(pos[A[i]],i);}writi(ans);return 0;
}