arc165F
题目描述：
给定 \(n\) 和一个长度为 \(2n\) 的序列 \(a\)，满足 \([1,n]\) 每个数恰好出现两次。
每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列 \(a\) 满足 \(\forall i\in[1,n]\ a_{2\times i}=a_{2\times i+1}\)。
在保证为最小操作次数的前提下，输出所有可以得到序列中字典序最小的那一个。
对于 \(100\%\) 的数据，满足：\(1≤n≤2×10^5\)。
题目分析：
先不考虑字典序最小，考虑操作数最小怎么得到。
若只有两个数，那么可能出现的情况只有两种：\(1221\) 和 \(1212\)。
显然第一个变成 \(1122\) 和 \(2211\) 的操作数最小，第二个变成 \(1122\) 的操作数最小。
扩展一下，对于一个数 \(i\)，第一次出现的位置记为 \(l_i\)，第二次出现的位置记为 \(r_i\)。
那么对于任意的 \(i,j\)，满足 \(l_i<l_j\) 并且 \(r_i<r_j\)，那么就让 \(i\) 向 \(j\) 连边，最后求一个最小拓扑序即可。
发现边的个数是 \(n^2\) 的，考虑怎么优化建图：
如果只有一维，即只有 \(l_i<l_j\)，可以直接排序后前缀优化建图。
但是现在有两维，分治把第一维给去掉，这样就可以 \(O(nlogn)\) 建图并且求解了。
代码：
点击查看代码
const int INF=1e9+7;
const int N=4e5+7;
int pos1[N],pos2[N],deg[N*50];
int n,a[N],L[N],R[N],tot,b[N];
vector<int> G[N*50];
bool cmp(int a,int b){
return L[a]<L[b];
}
void add(int u,int v){
G[u].p_b(v);
deg[v]++;
}
void solve(int l,int r){
if (l==r) return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
int posl=l,posr=mid+1;
for (int i=l;i<=mid;i++){
++tot;pos1[i]=tot;add(a[i],pos1[i]);
if (i!=l) add(pos1[i-1],pos1[i]);
}
for (int i=r;i>mid;i--){
++tot;pos2[i]=tot;add(pos2[i],a[i]);
if (i!=r) add(pos2[i],pos2[i+1]);
}
int cnt=l-1;
while(posl<=mid&&posr<=r){
if (R[a[posl]]<R[a[posr]]) add(pos1[posl],pos2[posr]),b[++cnt]=a[posl],posl++;
else b[++cnt]=a[posr],posr++;
}
while(posl<=mid) b[++cnt]=a[posl],posl++;
while(posr<=r) add(pos1[mid],pos2[posr]),b[++cnt]=a[posr],posr++;
for (int i=l;i<=r;i++) a[i]=b[i];
}
void topo(){
queue<int> q1;
priority_queue<int> q2;
for (int i=1;i<=tot;i++){
if (!deg[i]){
if (i<=n) q2.push(-i);
else q1.push(i);
}
}
while((!q1.empty())||(!q2.empty())){
int u;
if (q1.empty()) u=-q2.top(),q2.pop();
else u=q1.front(),q1.pop();
if (u<=n) printf("%d %d ",u,u);
for (auto v:G[u]){
deg[v]--;
if (!deg[v]){
if (v<=n) q2.push(-v);
else q1.push(v);
}
}
}
}
signed main(){
scanf("%d",&n);
for (int i=1;i<=2*n;i++){
int x=read();
if (!L[x]) L[x]=i;
else R[x]=i;
}
for (int i=1;i<=n;i++) a[i]=i;
sort(a+1,a+n+1,cmp);
tot=n;
solve(1,n);
topo();
return 0;
}