题解：P11670 [USACO25JAN] Cow Checkups S
chenxi2009
·
·
题解
本文含有二创成分。
我和乐土仙尊乃是至交好友！
你是蛊修世界中的一名蛊师，以传播大爱为己任。\
今天你收到至交好友乐土的传信，信中称他遭具羊、星宿两名魔头的围攻，恳求你速速送来一件关键蛊材助他脱困。
事实浮冰的形成十分繁琐，这需要你洞悉一种律道蛊方的所有变式。具体而言，这道蛊方由上、下两卷组成，每一卷均由 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）配对
考虑拆掉这个 $\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)$。
## 代码
```cpp
#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 的表情，双眼瞪大，感动地说不出话来。
又是传播大爱的一天呢。