啊啊啊宝宝你是一个可爱的有思维含量的分讨题
Tiat_Siba_Ignareo
·
·
题解
做完了 Simple Task，过了一段时间又想写分讨题，就找到了这里。
这个题也太难了（折磨了我好久好久呜呜），所以来写一篇详细的题解。
当然，如果你不是很无聊没题做，且你也不想锻炼你的代码能力，建议远离这道题目。
分析性质
先使用 ATcoder 传统艺能：找性质。
性质
____
证明：首先先证明，如果有，一定仅有连续的一段是未经操作的。这个很显然。因为我们只能往最左边或者右边放数，如果出现放的两段之间有一段没动过，且放的两段有至少一段不是最左或最右的，那么不是最左或最右的那一段根本就放不了数。
然后证明有一段是未经操作的。首先，一个数如果操作两次，那么操作总是可以用更少的次数等价替代掉，所以一个数最多只会操作一次。
那么只需要证明操作次数 $<3N$，显然如果操作 $3N$ 次，最中间那个数完全没必要动。所以操作次数一定 $<3N$，所以总存在一段。证毕。
____
那么，既然 $N$ 那么小，我们完全可以直接枚举保留的区间，然后就转化成了一个 check 的问题。我们需要在 $O(N^2)$ 时间内 check 出保留某段区间时是否有解。
容易发现一个优美的事实：$B$ 中每一个数是否进行了操作，进行了什么操作是唯一确定的。且无论以什么顺序操作，答案也是根据保留的区间唯一确定的。
假设我们枚举的保留区间是 $[l,r]$，那就把整个 $B$ 划成了三部分：$[1,l)$、$[l,r]$、$(r,3N]$。
这三部分的操作自然是：向左移、不动、向右移。那么，我们只要能够确定出操作的顺序，一切就都解决了。
## 图论建模
关键就在于判断有没有合法的操作顺序了。由于每个数只会被操作一次，左边和右边的相对顺序就是从中间往两边的。可以抽象成一个图，$u$ 向 $v$ 有一条有向边当且仅当 $u$ 在 $v$ 前面操作，那么这个图的拓扑排序就是一组合法解。只要让这个图无环就可以了。
等等……相对顺序？这四个字提示性极强，直接指向另外四个字——图论建模！
接下来我们就来分析还有哪些相对顺序。最好想的就是同色三个数的相对顺序，我们从这里入手。
## 分类讨论
不妨用 Left、Middle、Right 来代表左移、放中间不动、右移三种操作。来分类讨论每种情况：
（下面的图中，指向 L 和 R 的边对应的是从左往右对应数的操作，$123$ 则是操作顺序，M 不操作就不连边，不考虑操作顺序）
### 一、LLL
如图，可以发现 $3$ 无论如何都不能被移动到左边，所以这种情况一旦出现就无解。
### 二、RRR
对称，所以同理，$3$ 不能被移动到右边，所以也是一旦出现就无解。
### 三、LLM
这样显然是合法的。不存在其他方案。
### 四、MRR
这样显然是合法的。不存在其他方案。
### 五、LMM
如图，方案唯一。
### 六、MMR
如图，方案唯一。
### 七、MMM
最简单的情况，根本不用动。
### 八、LLR
会发现有两种情况。
第一种：
第二种：
但是无论哪一种，都有 R 在最后一个 L 前面，不妨只加这一个约束。
### 九、LRR
同理，也是两种情况。
第一种：
第二种：
依然同理，无论哪一种，都有 L 在最后一个 R 前面，不妨只加这一个约束。
### 十、LMR
这是本题的核心，也是最大的难点。
第一种：
第二种：
这种情况就没什么性质了，所以我们需要通过 2-SAT 来判断是否存在一种合法的顺序。
## 2-SAT 图构造
我们需要用一种常见的方式——边转点。
我们知道，前面我们确定操作顺序的方式是位置之间连边。现在我们要确定第十种情况是先右后左还是先左后右。
我们不妨建一个新图用 $[1,N]$ 号点表示第 $i$（$1 \leq i \leq N$）种颜色是否是先右后左（不妨把原图左边的点往上放，称为向上连边），用 $[N + 1, 2N]$ 号点表示第 $i - N$（$N + 1 \leq i \leq 2N$）种颜色是否是向下连。
详细讲一下新图的结构：$[2, l - 1]$ 在上面，每一个点向左连边；$[r + 1, 3N - 1]$ 在下面，每一个点向右连边；上下有一些特殊边。
接下来，只要把边连出来就可以了！
## 合法判断（难点）
首先前面我们讲过了，出现 LLL 或者 RRR 一定无解。
然后来分析还有什么情况是无解的。
### LLR 和 LRR
由于新图只涉及 LMR，在旧图上考虑。
可以发现，LLR 一定是向上连，LRR 一定是向下连。那么如果 LLR 在 LRR 右边，就会有下、右、上、左形成环。这种情况一定是无解的。
类似这样（不用管编号）：
### LMR 和 LLR/LRR
显然，如果 LMR 在 LLR 左边或者 LRR 右边，就一定要和 LLR 或 LRR 同向，否则就会形成环。图和上面其实是一样的，只不过 LMR 取代了其中一条边，我们要为 LMR 定向。那么这个时候在新图上让不可能的方向向可能的方向连一条边，也就是说当取到了不可能的方向就一定无解。
### LMR 和 LMR
那显然，两条边要同向，左边的边向下了，右边的边就不能向上；右边的边向上了，左边的边就不能向下。在新图上连边即可。
____
上面这几部分复杂度为 $O(N^2)$。
### MMM、LMM、MMR、LLM、MMR
这五种情况要判断是否有一个 M 是合法的。我们对于 $l \leq i \leq r$ 的 $B_i$ 进行讨论，维护一个指针从左往右扫 $A$。需要基础的贪心。
显然指针不会往左，因为不移动的情况下相对顺序是不改变的，所以这部分复杂度为 $O(N)$。
#### MMM
找到和当前 $B_i$ 同色的配对就可以了。尽可能左边一定不劣。
#### LMM
用 $1,2,3$ 表示三个相同的数从左到右的顺序。那么 $B$ 中的 $1,2,3$ 对应 $A$ 中的 $2,1,3$。
所以只有 $A$ 中最左/右两个位置的可以配掉。
#### MMR
是对称的。$B$ 中的 $1,2,3$ 对应 $A$ 中的 $1,3,2$。
所以依旧只有 $A$ 中最左/右两个位置的可以配掉。
#### LLM
可以发现这种情况相对顺序不改变，非常好判。
#### MRR
对称，相对顺序也是不改变的。
至此，这几种情况也解决掉了，下面还有 LMR 的两个判断，是本题最难也是最烦的部分。
### LMR 的 M 与其他 M 之间的限制
其他的 M 都已经被处理掉了，假设左边的 M 在 $A$ 中位置是 $p_l$，右边的 M 是 $p_r$，那么当前 M 的位置 $p_i$ 一定有 $p_l<p_i<p_r$。
首先有如果 $R < p_l$ 或者 $L > p_r$，显然是无解的。
来分类讨论其他几种情况：
#### $R>p_r
分四种情况讨论。
若 p_r 在右半部分：
向下连边显然错位了：
向上连呢？
是可以的！
那如果 p_r 在左半部分呢？
分析向上连：
依旧是可以的。
向下连：
错位了。
L<p_l
是对称的，用基本相同的方法分四种情况讨论就可以了，懒得画图了呜呜。
其余情况
会发现对建边没有限制。
LMR 的 M 与 LMR 的 M 之间的限制
显然两个 M 位置顺序不能变，没有其他要求。
假设有 l \leq i<j \leq r，B_i \neq B_j。设 L_i,R_i,L_j,R_j 为 B_i 和 B_j 在 A 中对应的左右两个位置。
那么（有了前面的位置对应关系，这一部分相信可以自行画图，我画图比较麻烦，因为有 12 种情况，草稿纸上的图没法拍照，所以只给结论）：
R_j<L_i
必定是越位的。无解。
L_j<L_i
#### $R_j<R_i
#### $L_j<R_i
____
恭喜你建完了所有的边，现在，跑一个 2-SAT 就做完了。
::::info[代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, N, a[105], b[105], status[105], L[105], R[105], aL[105], aR[105];
int tim, scnt, dfn[205], low[205], col[205], ins[205], pos[205], ans;
vector<int> LLL, RRR, LLR, LRR, LLM, MRR, LMM, MMR, MMM, LMR;//十种情况
vector<int> G[205], vec[205];
stack<int> S;
void genans(int now){
if (ans == -1)
ans = now;
else
ans = min(ans, now);
}
void add(int u, int v){
G[u].emplace_back(v);
}
void clr(){//清空
LLL.clear();
RRR.clear();
LLR.clear();
LRR.clear();
LLM.clear();
MRR.clear();
LMM.clear();
MMR.clear();
MMM.clear();
LMR.clear();
tim = 0;
memset(L, 0, sizeof L);
memset(R, 0, sizeof R);
memset(aL, 0, sizeof L);
memset(aR, 0, sizeof R);
memset(status, 0, sizeof status);
memset(pos, 0, sizeof pos);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(col, 0, sizeof col);
memset(ins, 0, sizeof ins);
while (!S.empty())
S.pop();
for (int i = 1; i <= 200; i++){
G[i].clear();
vec[i].clear();
}
}
void Tarjan(int u){
dfn[u] = low[u] = ++tim;
S.push(u);
ins[u] = 1;
for (auto v : G[u]){
if (!dfn[v]){//树边
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if (ins[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]){
scnt++;
while (1){
int v = S.top();
S.pop();
col[v] = u;
ins[v] = 0;
if (u == v)
break;
}
}
}
void genstatus(int l, int r){
for (int i = 1; i <= N; i++){
if (i < l)
status[i] = 1;
else if (l <= i && i <= r)
status[i] = 2;
else if (i > r)
status[i] = 3;
}
for (int i = 1; i <= N; i++){//处理出每种颜色的位置
vec[b[i]].emplace_back(i);
if (status[i] == 1){
if (!L[b[i]])
L[b[i]] = i;
}else if (status[i] == 3)
R[b[i]] = i;
if (!aL[a[i]])
aL[a[i]] = i;
aR[a[i]] = i;
}
}
int GetType(int i){//获取一个颜色的类型
int cntL = 0, cntM = 0, cntR = 0;
for (int pos : vec[i]){
cntL += (status[pos] == 1);
cntM += (status[pos] == 2);
cntR += (status[pos] == 3);
}
if (cntL == 3)//按照十种情况分类
return 1;//LLL
else if (cntR == 3)
return 2;//RRR
else if (cntL == 2 && cntR == 1)
return 3;//LLR
else if (cntL == 1 && cntR == 2)
return 4;//LRR
else if (cntL == 2 && cntM == 1)
return 5;//LLM
else if (cntM == 1 && cntR == 2)
return 6;//MRR
else if (cntL == 1 && cntM == 2)
return 7;//LMM
else if (cntM == 2 && cntR == 1)
return 8;//MMR
else if (cntM == 3)
return 9;//MMM
else if (cntL == 1 && cntR == 1 && cntM == 1)
return 10;//LMR
}
void RubbishSorting(int l, int r){
for (int i = 1; i <= n; i++){
int cntL = 0, cntM = 0, cntR = 0;
for (int pos : vec[i]){
cntL += (status[pos] == 1);
cntM += (status[pos] == 2);
cntR += (status[pos] == 3);
}
if (cntL == 3)//按照十种情况分类
LLL.emplace_back(i);
else if (cntR == 3)
RRR.emplace_back(i);
else if (cntL == 2 && cntR == 1)
LLR.emplace_back(i);
else if (cntL == 1 && cntR == 2)
LRR.emplace_back(i);
else if (cntL == 2 && cntM == 1)
LLM.emplace_back(i);
else if (cntM == 1 && cntR == 2)
MRR.emplace_back(i);
else if (cntL == 1 && cntM == 2)
LMM.emplace_back(i);
else if (cntM == 2 && cntR == 1)
MMR.emplace_back(i);
else if (cntM == 3)
MMM.emplace_back(i);
else if (cntL == 1 && cntR == 1 && cntM == 1)
LMR.emplace_back(i);
}
}
int check(int l, int r){
//钦定 L 上 R 下，向上连为 [1, n]，向下连为 [n + 1, 2n]
genstatus(l, r);
RubbishSorting(l, r);
//判断 LLL 和 RRR 的无解情况
if (LLL.size() || RRR.size())
return -1;
//LLL 最右侧的一个无法移到左边；RRR 对称，所以存在即无解
//判断 LRR 和 LLR 的无解情况
for (auto c1 : LRR)
for (auto c2 : LLR){
if (L[c1] < L[c2] && R[c1] < R[c2])
return -1;
}
//样例很良心给了这个，这样会成环
//判断 LMR 和 LLR/LRR 的情况
for (auto c1 : LMR){
for (auto c2 : LLR){
if (L[c1] < L[c2] && R[c1] < R[c2]){
//必须向上连
add(c1 + n, c1);
}
}
for (auto c2 : LRR){
if (L[c2] < L[c1] && R[c2] < R[c1]){
//必须向下连
add(c1, c1 + n);
}
}
}
//通过 LLR 和 LRR 可以唯一确定 LMR 的方向
//判断 LMR 和 LMR 的情况
for (auto c1 : LMR){
for (auto c2 : LMR){
if (L[c1] < L[c2] && R[c1] < R[c2])
add(c1 + n, c2 + n);
//左边向下，右边不能向上，否则成环
if (L[c2] < L[c1] && R[c2] < R[c1])
add(c1, c2);
//右边向上，左边不能向下，否则成环
}
}
//两个 LMR 需要同向
//判断 MMM、LLM、MRR、LMM、MMR 是否合法
int p = 1;
for (int i = l; i <= r; i++){//中间保留部分
int typ = GetType(b[i]);
if (typ == 9){//MMM
while (p <= N && a[p] != b[i])
p++;
if (p > N)
return -1;
pos[i] = p;
p++;
}else if (typ == 7){//LMM
while (p <= N && p != aL[b[i]] && p != aR[b[i]])
p++;
if (p > N)
return -1;
pos[i] = p;
p++;
}else if (typ == 8){//MMR
while (p <= N && p != aL[b[i]] && p != aR[b[i]])
p++;
if (p > N)
return -1;
pos[i] = p;
p++;
}else if (typ == 5){//LLM
while (p <= N && p != aR[b[i]])
p++;
if (p > N)
return -1;
pos[i] = p;
p++;
}else if (typ == 6){//MRR
while (p <= N && p != aL[b[i]])
p++;
if (p > N)
return -1;
pos[i] = p;
p++;
}
}
//处理出每个 M 在 a 中对应的位置
// 判断 LMR 的 M 限制
for (int i = l; i <= r; i++){
int x = GetType(b[i]);
if (x != 10)
continue;
//找到左边和右边被限制的位置，显然当前位置一定得在两个位置中间
int ml = 0, mr = N + 1;
for (int j = i - 1; j >= l; j--){
if (pos[j]){
ml = pos[j];
break;
}
}
for (int j = i + 1; j <= r; j++)
if (pos[j]){
mr = pos[j];
break;
}
//当前位置应该在 (ml, mr) 区间内
if (aL[b[i]] > mr || aR[b[i]] < ml)
return -1;
if (aL[b[i]] < ml){
//向下连
add(b[i], b[i] + n);
}
if (aR[b[i]] > mr){
//向上连
add(b[i] + n, b[i]);
}
}
//基于 M 的位置限制
// 显然有 LMR 和 LMR 之间的 M 不能相互越位，进行判断
for (int i = l; i <= r; i++){
int x = GetType(b[i]);
if (x != 10)
continue;
for (int j = i + 1; j <= r; j++){
int y = GetType(b[i]);
if (y != 10)
continue;
if (aR[b[j]] < aL[b[i]])
return -1;
if (aL[b[j]] < aL[b[i]]){
add(b[i], b[j] + n);
add(b[j], b[i] + n);
}
if (aR[b[j]] < aR[b[i]]){
add(b[i] + n, b[j]);
add(b[j] + n, b[i]);
}
if (aL[b[j]] < aR[b[i]]){
add(b[i] + n, b[j] + n);
add(b[j], b[i]);
}
}
}
//一定要搞清楚了
//Tarjan 主体
for (int i = 1; i <= n; i++)
if (!dfn[i])
Tarjan(i);
// 判断是否有解
for (int i = 1; i <= n; i++)
if (col[i] == col[i + n])
return -1;//矛盾了
return N - (r - l + 1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
N = 3 * n;
ans = -1;
bool qwq = 0;
for (int i = 1; i <= N; i++)
cin >> a[i];
for (int i = 1; i <= N; i++){
cin >> b[i];
if (a[i] != b[i])
qwq = 1;
}
if (!qwq){
cout << 0;
exit(0);
}
for (int len = N - 1; len; len--){
for (int l = 1; l + len - 1 <= N; l++){
clr();
int r = l + len - 1;
genans(check(l, r));
if (ans != -1){
cout << ans;
exit(0);
}
}
}
cout << ans;
return 0;
}
```
::::
## 后记
是微渺/的希望/我们依然前行没有光指引/往前吧失去吧不要停留。
这题确实很可怕，但是，把时间用在所热爱的一切上，用尽全力，总会看到成果的。