自动搬运

查看原文

来自洛谷，原作者为

	chenxi2009 身如柳絮随风扬。|粉福见专栏。|红名且勾支持互

搬运于2025-08-24 23:09:20，当前版本为作者最后更新于2025-02-05 21:10:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

本文含有二创成分。

我和乐土仙尊乃是至交好友！

你是蛊修世界中的一名蛊师，以传播大爱为己任。
今天你收到至交好友乐土的传信，信中称他遭具羊、星宿两名魔头的围攻，恳求你速速送来一件关键蛊材助他脱困。

事实浮冰的形成十分繁琐，这需要你洞悉一种律道蛊方的所有变式。具体而言，这道蛊方由上、下两卷组成，每一卷均由 $n$ 个凡蛊组成，上卷的凡蛊从左向右为 $a_1,a_2,\cdots,a_n$，下卷对应的蛊虫为 $b_1,b_2,\cdots,b_n$。蛊方的契合度为 $a_i=b_i$ 的位置 $i$ 的个数。

形成蛊方的变式需要你恰好做一次如下操作：选择两个正整数 $l,r$，将 $a_{l\cdots r}$ 翻转。
由于事实往往不是完美的，你只需要知道所有 $\frac{n(n+1)}{2}$ 种变式的契合度之和，而不需要给出具体每一种方案的契合度。

附加任务

事态紧急，若是有线性复杂度的方案就再好不过了。

思路

考虑统计每一对 $a_x=b_y$ 配对起来做出贡献的方案数。

$a_x$ 与 $b_x$ 配对

有两种情况可以使原本处在相同位置的两个蛊配对：它们不处在翻转范围内（$r<x$ 或 $x<l$），或它们是翻转操作的中心（$x=\frac{l+r}{2}$）。
前者分开计算翻转区间在 $x$ 左边和右边的的方案数，具体为：

$$\frac{x(x-1)}{2}+\frac{(n-x)(n-x+1)}{2}=\frac{x(x-1)+(n-x)(n-x+1)}{2} $$

后者计算以 $x$ 为中心的方案数即可，简单统计发现数量为 $\min(x,n-x+1)$。

$a_x$ 与 $b_y$（$x\ne y$）配对

$a_x$ 与 $b_y$ 配对当且仅当 $a_x$ 被翻转到了 $a_y$ 的位置，我们不妨钦定 $x<y$。显然要做到这一点操作必须是 $(x-m,y+m)$（$m$ 为自然数）的形式，根据边界 $x-m\ge1,y+m\le n$ 可得这样的方案有 $\min(x,n-y+1)$ 种。

考虑拆掉这个 $\min$，统计每一个 $x$ 或 $n-y+1$ 作为较小值被取了多少次。

可以发现 $x$ 作为较小值，代表的就是 $x$ 与序列左端的距离比 $y$ 离序列的右端的距离短，做出贡献的次数就是比 $x$ 更靠近中央的 $y$ 使 $a_x=b_y$ 的数量。$n-y+1$ 的贡献同理。

当然 $a_y=b_x$ 也要统计。

整体来看，做法就是从中央向两边扩展，统计 $a$、$b$ 数组中已经被扩展部分中每个值的出现次数，每次加入一个 $a_x$、$b_x$，它做出贡献的次数就是在它之前另一个数组内相同的值出现的次数，每次做出贡献的量为 $\min(x,n-x+1)$。

可以参考代码理解，时间复杂度 $O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[600000],b[600000],cnta[600000],cntb[600000],l,r;
long long ans;
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++) scanf("%d",&b[i]);
    l = n / 2 + 1,r = n / 2;//从中央开始扩展
    for(int i = 1;i <= n;i ++) if(a[i] == b[i]) ans += min(i,n - i + 1) + (1ll * i * (i - 1) + 1ll * (n - i) * (n - i + 1)) / 2;//a_i = b_i 做出的贡献
    for(int i = 1;i <= (n + 1) / 2;i ++){//每次扩展往左往右都分别扩展一个长度
        if(++ r > n) break;//防越界
        ans += 1ll * (cntb[a[r]] + cnta[b[r]]) * (n - r + 1);//a_r 和 b_r 做出的贡献
        cnta[a[r]] ++,cntb[b[r]] ++;//统计 a_r 和 b_r 出现的次数
        if(-- l <= 0) break;
        ans += 1ll * (cntb[a[l]] + cnta[b[l]]) * l;//向左扩展，同理
        cnta[a[l]] ++,cntb[b[l]] ++;
    }
    printf("%lld",ans);
    return 0;
}

后记

在最关键的时刻，你终于来到了乐土身边，扭转了战局。

乐土抓住你的手臂做出/bx 的表情，双眼瞪大，感动地说不出话来。

又是传播大爱的一天呢。