题目链接:https://atcoder.jp/contests/abc233/tasks/abc233_f
题目大意:给你一个 1 1 1到 N N N 的全排列 P P P,再给你 M M M 种操作,第 i i i 种操作可以交换 P P P 中第 a i a_i ai 和第 b i b_i bi 个元素。问你是否可以在 5 × 1 0 5 5\times10^5 5×105 次操作内把 P P P 交换成升序。如果可以,输出一种可行的方案。
简要分析:
首先判断一下到底有没有符合要求的可行方案。
类似于冒泡排序,考虑最坏的情况,
P
P
P是完全逆序的,那么要交换的次数为:
999
+
998
+
.
.
.
.
+
2
+
1
=
499500
<
500000
999 + 998 + .... +2 + 1 = 499500 < 500000
999+998+....+2+1=499500<500000,所以操作次数的限制就不用管了,放心大胆地去交换吧。
我们把每种操作看成一条连接
a
i
a_i
ai 和
b
i
b_i
bi 的无向边,这样会可能会形成很多个联通块,第
i
i
i个节点上的数字是
P
i
P_i
Pi ,那么排好序后数字
P
i
P_i
Pi 所处的节点一定是
P
i
P_i
Pi。如果想要有可行方案,就需要满足:对于所有的数字
P
i
P_i
Pi 它当前所在的节点
i
i
i和它最终要去的节点
P
i
P_i
Pi应该是在同一个联通块内的。这点可以用并查集方便实现。另外,我们在加边的时候,如果这两个节点已经联通了,那就不要在加这条边了,我们最终要的是树,因为树就可以保证连通性了。这题的特点就是点很少,边很多,如果我们不删去一些边的话,后续会操作的时间复杂度会很难看。
然后就可以进行交换了,交换的时候先从叶子节点入手,因为叶子节点一旦到了最终位置就不用管了,因为后续其他节点的交换是不会影响到它的。这点可以用DFS来操作,在DFS的时候,我们先把它的所有儿子都给安排好位置,最后再安排它自己。如何安排?用DFS。用DFS找到一条连接
i
i
i和
P
i
P_i
Pi的路径,沿着这条路径把
P
i
P_i
Pi交换到自己的位置,同时记录下每次操作的编号。
正解 并查集+DFS 的代码我就不贴了,可以看看其他人的文章。
由于最近在学习动态树(Link Cut Tree) ,所以就突发奇想,为什么不写个动态树练习练习呢?而且那个"找到一条
i
i
i和
P
i
P_i
Pi之间的路径,这不就是动态树的"split"函数吗?split后把
i
i
i和
P
i
P_i
Pi放到同一个splay里,再用中序遍历展开成原树,这不就很方便地找到路径了吗。写完之后由于不太熟练忘记pushdown操作,结果一直wa,搞了我半天心态。
Tip:在处理这类有边权的问题时,可以把边也当成节点处理,这样找到路径后就可以方便记录答案了,具体实现可以看下代码。
代码:
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pw(a) (1<<a)
#define PP push_back
#define X first
#define Y second
using namespace std;
typedef long long LL;
typedef double DD;
typedef pair<int,int> PAIR;
const int INF=1e9;
const int mod=1e9+7;
const int N=2e5+10;
int n,m,k,T,sum;
vector<int>ans;
vector<int>gra[N];
int vis[N];
int A[N];//A[i] 数字i在哪个位置
struct Node
{
int s[2],v,p;
int rev;
}tre[N<<4];//tre[i].v 节点i上是数字v
void pushrev(int x)
{
swap(tre[x].s[0],tre[x].s[1]);
tre[x].rev^=1;
}
void pushdown(int x)
{
if(!tre[x].rev) return ;
pushrev(tre[x].s[0]);
pushrev(tre[x].s[1]);
tre[x].rev=0;
}
bool isroot(int x)
{
int p=tre[x].p;
return tre[p].s[0]!=x&&tre[p].s[1]!=x;
}
void update(int x)
{
if(!isroot(x)) update(tre[x].p);
pushdown(x);
}
void rotate(int x)
{
int y=tre[x].p,z=tre[y].p;
int k=tre[y].s[1]==x;
if(!isroot(y)) tre[z].s[tre[z].s[1]==y]=x;
tre[x].p=z;
tre[y].s[k]=tre[x].s[k^1],tre[tre[x].s[k^1]].p=y;
tre[x].s[k^1]=y,tre[y].p=x;
}
void splay(int x)
{
update(x);
while(!isroot(x))
{
int y=tre[x].p,z=tre[y].p;
if(!isroot(y))
{
if((tre[y].s[1]==x)^(tre[z].s[1]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
int z=x;
for(int y=0;x;y=x,x=tre[x].p)
{
splay(x);
tre[x].s[1]=y;
}
splay(z);
}
void makeroot(int x)
{
access(x);
pushrev(x);
}
int getroot(int x)
{
access(x);
while(tre[x].s[0]) pushdown(x),x=tre[x].s[0];
splay(x);
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
}
bool isconnect(int x,int y)
{
makeroot(x);
return getroot(y)==x;
}
void link(int x,int y)
{
makeroot(x);
if(getroot(y)!=x) tre[x].p=y;
}
//-------------上面都是动态树原汁原味的板子
void move(int x,int i)//中序遍历交换
{
pushdown(x);//关键,一定要记得pushdown
if(tre[x].s[0]) move(tre[x].s[0],i);
if(!tre[x].v) ans.PP(x);//没有值,说明它是边
else
{
int j=tre[x].v;
swap(tre[A[i]].v,tre[x].v);
swap(A[i],A[j]);
}
if(tre[x].s[1]) move(tre[x].s[1],i);
}
void dfs(int u)
{
vis[u]=1;
for(int v:gra[u])
if(!vis[v]) dfs(v);
split(A[u],u);//安排叶子节点
move(u,u);
}
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tre[i].v;
A[tre[i].v]=i;
}
cin>>m;
for(int i=1,x,y;i<=m;i++)
{
cin>>x>>y;
if(isconnect(x,y)) continue;
gra[x].PP(y);
gra[y].PP(x);
link(x,i+n);//第i条边的编号时i+n
link(y,n+i);
}
for(int i=1;i<=n;i++)
{
if(!isconnect(A[i],i))
{
puts("-1");
return 0;
}
}
for(int i=1;i<=n;i++)
if(!vis[i]) dfs(i);
cout<<ans.size()<<endl;
for(int v:ans) cout<<v-n<<' ';
return 0;
}