题解：P16926 「LAOI-13」Deadlocked
lailai0916
·
·
题解
题意简述
构造两个长度为 n 的排列 P,Q，
使它们的最长上升子序列长度分别为 x,y。
对每个位置连接 P_i,Q_i，
还要求所得无向图恰有 k 个连通块。
解题思路
令置换 S 满足 S(P_i)=Q_i。
每个点在图中的两条关联边都来自 S，
所以图的连通块数就是置换 S 的环数。
一个含 k 个环的置换可以用 n-k 次交换变成恒等置换。
交换排列中的两个位置，LIS 长度至多改变 2。
因此，可行的必要条件为：
|x-y|\le2(n-k)
当 x,y 都属于 \{1,n\} 时，排列被唯一确定。
若 x=y，只能取 k=n。
若 \{x,y\}=\{1,n\}，升序与降序排列之间形成翻转置换，
故只能取 k=\lceil n/2\rceil。
除这些边界情形外，上述必要条件也是充分条件。
不妨交换两个排列，使 x\le y。
记 L(l,r) 为 l,l+1,\dots,r，
记 R(r,l) 为 r,r-1,\dots,l。
若左端点超过右端点，就将这一段视为空序列。
一个连通块。 当 k=1 且 y<n 时，
令 d=n-y，c=\left\lfloor\frac{y-x+1}{2}\right\rfloor。
构造：
P=L(1,x-1),R(n,x)
另一个排列为：
Q=L(2,x),L(x+d,x+d+c-1),1,L(x+d+c,n),R(x+d-1,x+1)
按五个单调段比较首尾值，可得 $Q$ 的 LIS 为 $y$。
沿映射 $P_i\mapsto Q_i$ 依次追踪这些区间，
所有数恰好组成一个置换环。
当 $k=1$ 且 $y=n$ 时，令：
$$
c=\left\lfloor\frac{n-x}{2}\right\rfloor
$$
取 $Q=L(1,n)$，并构造：
$$
P=L(2,x),R(n,x+c+1),1,R(x+c,x+1)
$$
同样按单调段可直接验证，$P$ 的 LIS 为 $x$，
且 $P$ 自身是一个置换环。
**处理 $x=1$。** 固定 $P=R(n,1)$，
并令 $S$ 为 $Q$ 的逆序。
此时 $Q$ 的 LIS 等于 $S$ 的最长下降子序列长度，
图的连通块数等于 $S$ 的置换环数。
若目标下降子序列长度为 $n-1$，令：
$$
t=\left\lceil\frac{n+1}{2}\right\rceil-k
$$
构造：
$$
S=(t+1),R(n,t+2),R(t,1)
$$
其最长下降子序列长度为 $n-1$。
追踪首段与两个降序段可得环数为 $k$。
对于其余情况，令 $d=n-y$。
若 $k\le d$，在 $S$ 前加入 $k-1$ 个不动点，
剩余部分归约到 $k=1$。
否则加入 $d-1$ 个不动点，
剩余规模为 $y+1$，归约到下降长度为规模减一的情形。
这些不动点的值小于后缀中的所有值，
不会增加后缀的最长下降子序列，
并且每个不动点恰好增加一个置换环。
**两个小型基形。** 当 $x=y=2$ 时，取：
$$
P=1,R(n,2)
$$
若 $k=n$，令 $Q=P$；否则令：
$$
Q=2,R(n,n-k+2),1,R(n-k+1,3)
$$
当 $x=2,y=n$ 时，取 $Q=L(1,n)$。
若 $k=\lceil(n+1)/2\rceil$，令 $P=1,R(n,2)$。
否则令：
$$
t=\left\lfloor\frac{n-1}{2}\right\rfloor-k+1
$$
构造：
$$
P=2,R(n,n-t+1),1,R(n-t,3)
$$
这些排列都只含少量单调段。
逐段比较即可得到所需 LIS，
而直接追踪置换映射可得到恰好 $k$ 个环。
**公共前缀归约。** 同时在 $P,Q$ 前加入：
$$
1,2,\dots,t
$$
并将剩余元素整体增加 $t$。
两个 LIS 长度和连通块数都会增加 $t$。
若 $y=n$，根据 $k<x-1$ 是否成立，
分别加入 $k-1$ 或 $x-2$ 个公共前缀，
归约到 $k=1$ 或 $x=2,y=n$。
若 $x=y$，采用相同的前缀长度，
归约到 $k=1$ 或 $x=y=2$。
若 $1<x<y<n$，当 $k\le x-1$ 时加入 $k-1$ 个，
否则加入 $x-1$ 个，归约到 $k=1$ 或 $x=1$。
每次归约都严格减小规模，并落入已经证明的基形。
这说明必要条件覆盖了所有非边界情形。
每个数只会被写入常数次。
时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
struct Ans
{
vi p,q;
};
void inc(vi &a,int l,int r)
{
for(int i=l;i<=r;i++)a.push_back(i);
}
void dec(vi &a,int r,int l)
{
for(int i=r;i>=l;i--)a.push_back(i);
}
Ans one(int n,int x,int y)
{
vi a,b;
if(y<n)
{
int d=n-y,c=(y-x+1)/2;
inc(a,1,x-1);
dec(a,n,x);
inc(b,2,x);
inc(b,x+d,x+d+c-1);
b.push_back(1);
inc(b,x+d+c,n);
dec(b,x+d-1,x+1);
}
else
{
int c=(n-x)/2;
inc(a,2,x);
dec(a,n,x+c+1);
a.push_back(1);
dec(a,x+c,x+1);
inc(b,1,n);
}
return {a,b};
}
vi make_s(int n,int y,int k)
{
if(k==1)
{
Ans res=one(n,1,y);
reverse(res.q.begin(),res.q.end());
return res.q;
}
if(y==n-1)
{
int t=(n+2)/2-k;
vi s;
s.push_back(t+1);
dec(s,n,t+2);
dec(s,t,1);
return s;
}
int t=n-y,r=k<=t?k-1:t-1;
vi s;
inc(s,1,r);
vi sub=make_s(n-r,y,k-r);
for(auto v:sub)s.push_back(v+r);
return s;
}
Ans low(int n,int y,int k)
{
vi a,b=make_s(n,y,k);
dec(a,n,1);
reverse(b.begin(),b.end());
return {a,b};
}
Ans two(int n,int k)
{
vi a,b;
a.push_back(1);
dec(a,n,2);
if(k==n)return {a,a};
b.push_back(2);
dec(b,n,n-k+2);
b.push_back(1);
dec(b,n-k+1,3);
return {a,b};
}
Ans full(int n,int k)
{
vi a,b;
inc(b,1,n);
if(k==(n+2)/2)
{
a.push_back(1);
dec(a,n,2);
return {a,b};
}
int t=(n-1)/2-k+1;
a.push_back(2);
dec(a,n,n-t+1);
a.push_back(1);
dec(a,n-t,3);
return {a,b};
}
Ans build(int n,int x,int y,int k);
Ans pre(int n,int x,int y,int k,int t)
{
Ans res=build(n-t,x-t,y-t,k-t);
vi a,b;
inc(a,1,t);
inc(b,1,t);
for(auto v:res.p)a.push_back(v+t);
for(auto v:res.q)b.push_back(v+t);
return {a,b};
}
Ans build(int n,int x,int y,int k)
{
if(k==1)return one(n,x,y);
if(x==1)return low(n,y,k);
if(x==2&&y==2)return two(n,k);
if(x==2&&y==n)return full(n,k);
if(y==n)
{
int t=k<x-1?k-1:x-2;
return pre(n,x,y,k,t);
}
if(x==y)
{
int t=k<x-1?k-1:x-2;
return pre(n,x,y,k,t);
}
int t=k<=x-1?k-1:x-1;
return pre(n,x,y,k,t);
}
void print(const vi &a)
{
int n=a.size();
for(int i=0;i<n;i++)
{
if(i)cout<<' ';
cout<<a[i];
}
cout<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n,x,y,k;
cin>>n>>x>>y>>k;
bool rev=0;
if(x>y)
{
swap(x,y);
rev=1;
}
bool ok=1;
Ans ans;
if((x==1||x==n)&&(y==1||y==n))
{
if(x==y&&k==n)
{
if(x==1)
{
dec(ans.p,n,1);
ans.q=ans.p;
}
else
{
inc(ans.p,1,n);
ans.q=ans.p;
}
}
else if(x==1&&y==n&&k==(n+1)/2)
{
dec(ans.p,n,1);
inc(ans.q,1,n);
}
else ok=0;
}
else if(y-x>2*(n-k))ok=0;
else ans=build(n,x,y,k);
if(!ok)
{
cout<<"NO"<<'\n';
continue;
}
if(rev)swap(ans.p,ans.q);
cout<<"YES"<<'\n';
print(ans.p);
print(ans.q);
}
return 0;
}
```