题解：P14925 [北大集训 2025] 异形工厂

· · 题解

发现每一次操作本质就是交换 s_i 和 s_{i+1} 或者交换 s_i 和 s_{i+2}。那么如果我们只考虑 1 的位置，其实每一次的操作就是位置 +1 或者 +2。那么我们考虑把两边的所有 1 提取出来，假设下标分别为 s_i 和 t_i，那么我们想要尽量最小化 \sum \lceil \frac{s_i - t_{p_i}}{2} \rceil。其中 p 为一个排列。

发现如果有这个上取整很麻烦，所以先不考虑它。首先只有 0 \to 1 和 1 \to 0 的情况需要管，然后我们分别给他赋 1 和 -1 的权值。所以一个区间合法当且仅当 l-1 处的前缀和和 r 的前缀和相等。然后我们就考虑把一个大区间拆成若干个不可分割，且左右端点处的前缀和相等的区间，然后我们只需要处理这些区间即可。

对于一个区间，我们发现一个 0 \to 1 需要和一个 1 \to 0 进行交换，所以我们考虑一个匹配问题。我们发现其实就是把前缀和的折线画出来之后所围成的面积的大小。维护这个东西只需要维护前缀和以及 \sum^i_{j=1}(a_j-b_j) \times j 即可。

接下来把可能会额外增加的 \frac{1}{2} 的贡献加回来。我们贪心的去考虑，尽量去匹配奇偶性和自己相同的另一边，且尽量去匹配往后的数。这里我们可以对于奇数下表和偶数下表分别开一个 BIT 然后再在树状数组上二分就可以模拟匹配。然后我们再让所有被当前这一对匹配包含的匹配因为前面少了一个数，所以他的奇偶性就会有变化，然后再额外用一个 BIT 来维护额外增加的 \frac{1}{2} 数量。

最后的复杂度为 \mathrm O(n \log n)。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e6 + 10;
const int V = 1e6;

struct BIT
{
    int c[maxn];
    void init(){memset(c,0,sizeof(c));}
    int lowbit(int u){return u & (-u);}
    void update(int u,int val){while(u <= V){c[u] += val;u += lowbit(u);}}
    int query(int u){int ans = 0;while(u > 0){ans += c[u];u -= lowbit(u);}return ans;}
    int Find()
    {
        int p = 0,sum = 0;
        for(int i = 18;i >= 0;i--)if(sum + c[p | (1 << i)])p |= (1 << i),sum += c[p];
        return p + 1;
    }
}C[2],W;
int res[maxn],ans[maxn],sp[maxn];map<int,int> mp;
int n,q,a[maxn],b[maxn],sum[maxn],pre[maxn];

void solve()
{
    C[0].init();C[1].init();W.init();
    int cnt = 0;
    for(int i = 1;i <= n;i++)
    {
        if(a[i] > b[i])cnt++,C[i & 1].update(1,1),C[i & 1].update(cnt + 1,-1);
        else if(cnt && a[i] < b[i])
        {
            int k = C[i & 1].Find();C[i & 1].update(1,-1);C[i & 1].update(k,1);
            C[!(i & 1)].update(k,-1);C[!(i & 1)].update(cnt + 1,1);
            W.update(k,1);W.update(cnt + 1,-1);res[i] += W.query(cnt) + abs(sp[i] - sp[pre[i]]);
            W.update(cnt,-W.query(cnt));W.update(cnt + 1,-W.query(cnt + 1));cnt--;
        }
    }
}

signed main()
{
    cin >> n >> q;mp[0] = 0;
    for(int i = 1;i <= n;i++){char c;cin >> c;a[i] = c - '0';}
    for(int i = 1;i <= n;i++){char c;cin >> c;b[i] = c - '0';}
    for(int i = 1;i <= n;i++)
    {
        sp[i] = sp[i - 1] + (a[i] - b[i]) * i;
        sum[i] = sum[i - 1] + a[i] - b[i];
        pre[i] = mp[sum[i]];mp[sum[i]] = i;
    }
    solve();
    for(int i = 1;i <= n;i++)swap(a[i],b[i]);
    solve();
    for(int i = 1;i <= n;i++)ans[i] = ans[pre[i]] + res[i] / 2;
    while(q--)
    {
        int l,r;cin >> l >> r;
        if(sum[r] != sum[l - 1])cout << "-1\n";
        else if(l + 1 == r && a[l] != b[l])cout << "-1\n";
        else cout << ans[r] - ans[l - 1] << '\n';
    }
    return 0;
}