题解：P11710 「KTSC 2020 R2」一二三

· · 题解

设 (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);
            }
        }
    }
}