ARC165F Make Adjacent

【题解】ARC165F Make Adjacent

题目描述：

给定 $n$ 和一个长度为 $2n$ 的序列 $a$，满足 $[1,n]$ 每个数恰好出现两次。
每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列 $a$ 满足 $\forall i\in[1,n] \quad a_{2i} = a_{2i-1}$。
$1 \le n \le 2 \times 10^5$

题目分析：

若只有两个数，则本质上只有下面这两种情况：$1212$ 和 $1221$
可以发现对于第一种情况，最小的操作次数必然是变成 $1122$，而第二种则可以变成 $1122$ 或者 $2211$ 均可。
扩展一下，也就是说设 $l_i$ 表示 $i$ 第一次出现的位置，$r_i$ 表示 $i$ 最后一次出现的位置。
若存在 $l_i < l_j$ 且 $r_i < r_j$，则 $i$ 必然排在 $j$ 的前面。
暴力就是 $O(n^2)$ 建边然后跑最小拓扑序即可。
优化的话有以下两种做法。

做法一：
考虑如果只有 $l_i < l_j$ 这一维的限制很好做，就是前缀和优化建图。
既然一维我们会了，二维就是对第一维分治，这样就转化为了只剩一维限制的了。

做法二：
考虑这个其实就是一个二维偏序，所以可以使用线段树优化建图，也就是按照 $l$ 排序之后在线段树上维护 $r$。
但是我们因为存在 $l$ 的限制，所以我们不能只在一棵线段树上操作，要对线段树可持久化，这样才能保证贡献是对的。

代码：

做法一：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[100 * N];
int cnt,head[50 * N],tot,pos1[N],pos2[N],a[N],b[N],deg[50 * N],L[N],R[N];
void add_edge(int from,int to){
//	printf("%d %d\n",from,to);
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
	deg[to]++;
}
bool cmp(int a,int b){
	return L[a] < L[b];
}
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_edge(a[i],pos1[i]);
		if(i != l)	add_edge(pos1[i-1],pos1[i]);
	}
	for(int i=r; i>=mid+1; i--){
		++tot;pos2[i] = tot;add_edge(pos2[i],a[i]);
		if(i != r)	add_edge(pos2[i],pos2[i+1]);
	}
	int sz = l-1;
	while(posl <= mid && posr <= r){  //归并 
		if(R[a[posl]] < R[a[posr]])	add_edge(pos1[posl],pos2[posr]),b[++sz] = a[posl],++posl;
		else	b[++sz] = a[posr],++posr;
	}
	while(posl <= mid)	b[++sz] = a[posl],++posl;
	while(posr <= r)	add_edge(pos1[mid],pos2[posr]),b[++sz] = a[posr],++posr;
	for(int i=l; i<=r; i++)	a[i] = b[i];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%d",&n);
	for(int i=1; i<=2*n; i++){
		int x;scanf("%d",&x);
		if(!L[x])	L[x] = i;
		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);
	
	queue<int> q1;priority_queue<int,vector<int>,greater<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 now;
		if(!q1.empty())	now = q1.front(),q1.pop();
		else	now = q2.top(),q2.pop();
		if(now <= n)	printf("%d %d ",now,now);
		for(int i=head[now]; i; i=e[i].nxt){
			int to = e[i].to;
			deg[to]--;
			if(!deg[to]){
				if(to <= n)	q2.push(to);
				else	q1.push(to);
			}
		}
	}
	return 0;
}

做法二：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[100 * N];
int l[N],r[N],cnt,tot,pos[100 * N],head[100 * N],deg[100 * N],a[N],ls[100*N],rs[100*N];
void add_edge(int from,int to){
//	printf("%d %d\n",from,to);
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
	deg[to]++;
}
bool cmp(int a,int b){
	return l[a] < l[b];
}
void modify(int &now,int now_l,int now_r,int x,int y){
	if(now){
		++tot;ls[tot] = ls[now],rs[tot] = rs[now];
		now = tot;
	}
	else	++tot,now = tot;
	if(now_l == now_r){
		add_edge(y,now);
		return;
	}
	int mid = (now_l + now_r)>>1;
	if(x <= mid)	modify(ls[now],now_l,mid,x,y);
	if(x > mid)		modify(rs[now],mid+1,now_r,x,y);
	if(ls[now])	add_edge(ls[now],now);
	if(rs[now])	add_edge(rs[now],now);
}
void query(int now,int now_l,int now_r,int l,int r,int x){
	if(!now)	return;
	if(l <= now_l && now_r <= r){
		add_edge(now,x);
		return;
	}
	int mid = (now_l + now_r)>>1;
	if(l <= mid)	query(ls[now],now_l,mid,l,r,x);
	if(r > mid)		query(rs[now],mid+1,now_r,l,r,x);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%d",&n);
	for(int i=1; i<=2*n; i++){
		int x;scanf("%d",&x);
		if(!l[x])	l[x] = i;
		r[x] = i;
	} 
	for(int i=1; i<=n; i++)	a[i] = i;
	sort(a+1,a+n+1,cmp);
	tot = n;
	int rt = 0;
	for(int i=1; i<=n; i++){
		query(rt,1,2*n,1,r[a[i]]-1,a[i]);
		modify(rt,1,2*n,r[a[i]],a[i]);
	}
	
	queue<int> q1;priority_queue<int,vector<int>,greater<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 now;
		if(!q1.empty())	now = q1.front(),q1.pop();
		else	now = q2.top(),q2.pop();
		if(now <= n)	printf("%d %d ",now,now);
		for(int i=head[now]; i; i=e[i].nxt){
			int to = e[i].to;
			deg[to]--;
			if(!deg[to]){
				if(to <= n)	q2.push(to);
				else	q1.push(to);
			}
		}
	}
	return 0;
}