第一次打AGC，好难受。
T1 看了一眼题解，没看懂……但是还是做出来了。
T2 感觉比 T1 简单，构造很好猜。
其他的没时间思考，T1 花了我 2h30min，难受。
翻译：
给定长度为 \(3n\) 的序列，其中字母 ABC 各有 \(n\) 个。
一个合法序列 \(T\) 满足以下条件：
其长度为 \(3k (1 \le k \le n)\)。
\(T_1 = T_2 = ... = T_k\)
\(T_{k + 1} = T_{k + 2} = ... = T_{2k}\)
\(T_{2k + 1} = T_{2k + 2} = ... = T_{3k}\)
\(T_1, T_{k + 1}, T_{2k + 1}\) 互不相同。
求一个把这个序列分成不多于 \(6\) 个合法的序列的方案。
可以证明，一定存在一种合法的划分。
分三段考虑。
std 做法是关于 ABC 的 6 种排列，依次枚举，贪心选择。
我在考场上是：先考虑前两半，相异配对，网络流解决。
不会产生相同配对的正确性？由于是相异配对，如果产生相同配对，则某一个一定超过了 \(n\) 个，不符合题意。所以网络流可以解决，贪心选择没问题。
网络流只有 \(6 + 2\) 个点，所以可以看作常数，复杂度 + O(1)
所以整体复杂度 \(O(n)\)
妈的，傻逼网络流，真的服……
考虑如下转化：
也就是我们贪心把所有的 \(\overline{ABC}\) 放在最前面即可。（相当于删除）
由于拼接后也可能存在 \(\overline{ABC}\)，所以利用栈的思想处理。
复杂度 \(O(n)\)。
参考 AGC055C - Legitimity 的博客 - 洛谷博客 和补充 题解：AGC55C Weird LIS - Edward1002001 的博客 - 洛谷博客
这里再做一点说明。
无用点为什么不可连续？考虑 4 3 5 2 1 7 6，也就是 非 非 必 无 无 非 非。这个排列和 2 1 3 7 6 5 4 ，也就是 非 非 必 非 非 非 非 是等价的。也就是说，连续的 非 会使得我们重复计数。所以不可以连续。
ans 初始设置？其实枚举的是没有必经点的情况（全是非必经点），需要满足：
\(k \le \lfloor \frac n2 \rfloor\)
\(k \le m\)
\(k \ge 2\)
所以才有 \(\min(m, \lfloor \frac n2 \rfloor) - 1\)。但是我们还需要考虑当 \(m = n - 1\) 时，可以存在全是必经点的情况，也就是 1 2 3 ... n 的情况。
为什么 \(\min(m, x + y) - \max(x, 3) + 1\)？这里枚举的是 \(k\)，\(k\) 的下界确定了，因为存在 \(k - 1\)，所以 \(k - 1 \ge 2 \iff k \ge 3\)。
其他部分最终式子为：
参考 at_agc055_c Weird LIS 题解 - juruo - 洛谷博客
这里做一点解释：
状态机的设定，4种状态：
除了 CAN，都能放
只能放 CAN
可以放 MUST 或者 USELESS，之后 MUST 还可以跟 MAY
可以放 MUST 或者 USELESS，之后 MUST 不可以跟 MAY
为什么有状态4？因为 k 确定了红黑对的数量，而我们是贪心的把所有红黑对尽可能放在前面。而可能存在只有 非 非 无 必 的情况，所以有状态 3，通过 MUST 转移到 1，通过 USELESS 转移到 4，但是不能再来一个 MAY！
一道猜结论的题。
观察三个串，有 ABC，BCA，CAB，我们考察能划分成这三种串的串的性质。
考虑每一个字母出现的次数：由于 B 只在 BCA 中在 A 前面，其他的类似。我们考虑定义 \(M_B = \max S_B - S_A\)，其他的类似。
可以发现，\(M_B \le C_{BCA}\)，同理，得到 \(M_A + M_B + M_C \le C_{ABC} + C_{BCA} + C_{CAB} = N\)。
这是必要条件，所以考虑证明充分性（不会。
所以我们可以设出一个 \(O(n^7)\) 的 DP，令 \(f_{a, b, c, x, y, z}\) 表示 ABC 的数量以及 \(M_A, M_B, M_C\)。
不过考虑 \(a + b + c = i\) 的时候才有贡献，所以可以省一维，变为 \(O(n^6)\)。
神仙思路题。
我们把整个序列看作一个排列，每一次的合并相当于交换排列中的两个位置。
而最终 \(S_i \to [ \min_{j = i}^n P_j, \max_{j = 1}^i P_j]\)，一个后缀 \(\min\) 和一个前缀 \(\max\)。
考虑归纳法，分 \(P_i > P_{i + 1}\) 或者 \(P_i < P_{i + 1}\) 讨论。
最终就是求合法序列的最小逆序对数。考虑贪心放置，用数状数组求。
总复杂度 \(O(n + n \log n)\)，可以通过6指针的方法优化到 \(O(n + n)\)。