自动搬运

查看原文

来自洛谷，原作者为

	Lgx_Q 变强不如变菜

搬运于2025-08-24 23:09:40，当前版本为作者最后更新于2025-06-30 20:16:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $(1,2,3)$ 共 $u$ 组，$(3,2,1)$ 共 $v$ 组。

设 $m_1, m_2, m_3$ 为三种数字的出现次数，那么一个显然的条件为 $u + v \le \min(m_1, m_2, m_3)$。

观察匹配的性质，发现 $(1,2,3)$ 选取的一定是最前面的 $u$ 个 $1$ 和最后面的 $u$ 个 $3$，具体的，会让第 $1$ 个 $1$ 和第 $m_3 - u + 1$ 个 $3$ 匹配，第 $2$ 个 $1$ 和第 $m_3 - u + 2$ 个 $3$ 匹配等等。$(3,2,1)$ 同理。

那么我们容易扫描求出 $u$ 的上界 $u_0$ 和 $v$ 的上界 $v_0$。

这并不充分。现在给每对匹配分配一个 $2$，相当于有 $u + v$ 个区间，每个区间匹配一个位于区间内的 $2$。

我们先求出最大的 $u + v$，最后再构造方案。

使用 Hall 定理，相当于对于每个区间 $[l, r]$，被 $[l, r]$ 包含的匹配区间数量不超过 $[l, r]$ 中 $2$ 的个数。

枚举 $[l, r]$，我们根据区间内第一个 $1/3$ 和最后一个 $1/3$ 的标号（标号指这个 $1/3$ 是原序列中的第几个 $1/3$），容易求出 $u'$ 和 $v'$，表示当 $u \ge u' + 1$ 时 $[l, r]$ 内出现第一组 $(1,2,3)$，当 $v\ge v' + 1$ 时 $[l, r]$ 内出现第一组 $(3,2,1)$。

那么我们通过观察可以得出区间内 $(1,2,3)$ 的组数为 $\max(0, u - u')$，$(3,2,1)$ 同理。

求出 $cnt$ 表示 $[l, r]$ 内 $2$ 的个数，条件可以写作 $\max(0, u - u') + \max(0, v - v') \le cnt$。

可以拆成 $u\le u' + cnt$，$v\le v' + cnt$，$u + v\le u' + v' + cnt$ 三个条件。记一个 $s_0$ 表示 $u + v$ 的上界，那么用这三个值分别更新 $u_0,v_0,s_0$ 即可。

得到一组 $u + v$ 最大的 $(u, v)$ 之后，扫描一遍原序列，用一个 set 求出每个区间应该匹配哪个 $2$。时间复杂度 $\mathcal O(n ^ 2 + n\log n)$。

代码中变量名会有所差异。

ll n, a[maxn], b[maxn], m[4], ulim, vlim, slim, u, v;
set <ll> st; vector <ll> vec[4];

void maximize(vector <ll> A) {
    n = A.size();
    for(ll i = 0; i < n; i++) a[i + 1] = A[i];
    vec[1].pb(0), vec[2].pb(0), vec[3].pb(0);
    for(ll i = 1; i <= n; i++)
        b[i] = ++m[a[i]], vec[a[i]].pb(i);
    ulim = vlim = slim = min(min(m[1], m[3]), m[2]);
    for(ll i = 1, lst1 = 0, lst3 = 0; i <= n; i++)
        if(a[i] == 1) {
            if(lst3) chkmin(ulim, b[i] + m[3] - lst3 - 1);
            lst1 = b[i];
        } else if(a[i] == 3) {
            if(lst1) chkmin(vlim, b[i] + m[1] - lst1 - 1);
            lst3 = b[i];
        }
    for(ll l = 1; l <= n; l++) {
        ll cnt = 0, fir1 = 0, fir3 = 0, lst1 = 0, lst3 = 0;
        for(ll r = l; r <= n; r++) {
            if(a[r] == 2) ++cnt;
            else if(a[r] == 1) {
                fir1 || (fir1 = b[r]);
                lst1 = b[r];
            } else {
                fir3 || (fir3 = b[r]);
                lst3 = b[r];
            }
            if(!fir1 || !fir3) continue;
            ll u0 = fir1 + m[3] - lst3 - 1, v0 = fir3 + m[1] - lst1 - 1;
            chkmin(ulim, u0 + cnt), chkmin(vlim, v0 + cnt);
            chkmin(slim, u0 + v0 + cnt);
        }
    }
    u = min(ulim, slim), v = min(vlim, slim - u);
    for(ll i = 1; i <= n; i++) {
        if(a[i] == 2) st.insert(i);
        else if(a[i] == 1) {
            if(m[1] - b[i] + 1 <= v) {
                auto it = st.lower_bound(vec[3][b[i] - m[1] + v]);
                answer(vec[3][b[i] - m[1] + v] - 1, *it - 1, i - 1);
                st.erase(it);
            }
        } else {
            if(m[3] - b[i] + 1 <= u) {
                auto it = st.lower_bound(vec[1][b[i] - m[3] + u]);
                answer(vec[1][b[i] - m[3] + u] - 1, *it - 1, i - 1);
                st.erase(it);
            }
        }
    }
}