Cow Checkups (USACO Silver 2025 January)

题目复述：给定 $a_i$ , $b_i$ ( $i, a_i, b_i \leq 5 \cdot 10^5$ ), 对于所有 $1 \leq l \leq r \leq n$ ，将 $a_l, a_{l+1}, ..., a_r$ 反转，然后数有多少个 $i$ ，使得 $b_i=a_i$ ，求所有 $l,r$ 组合下的个数之和。

这是一道Prefix sum题。可以看到这个题对于复杂度要求比较高，仅仅能 $\mathcal{O}(1)$ 计算一个范围 $(l,r)$ 的贡献都不够。我们需要寻找对所有位置扫描一遍，然后对每个位置都能 $\mathcal{O}(1)$ 计算对最终结果的贡献的算法。

我们考虑每个 $a_i=b_j$ 的一对位置对，设 $c_{ij}$ 为这一对数字对最终的结果的贡献。我们观察，对于固定的 $i$ ， $c_{ij}$ 随着 $j$ 的变化，是分段常数或分段线性的，分段点在 $j=i$ 和 $j=N-i$ 。

设 $L=\min(i,n-i)$ , $R=\max(i,n-i)$ ，那么 $c_{ij}$ 可以分成四种情况：

$0 \leq j < L$ : $c_{ij} = j+1$
$L \leq j \leq R$ : $c_{ij} = L+1$
$R < j \leq N-1$ : $c_{ij} = N-j$
如果 $i = j$ ，除以上之外， $a_i, b_i$ 还在 $[l,r]$ 区间不包含 $i$ 时产生贡献: $c_{ij}$ += $i*(i+1)/2 + (N-1-i)*(N-i)/2$

有了这个之后，我们可以对 $i$ 循环，用prefix sum来 $\mathcal{O}(1)$ 计算对于这个 $i$ 的所有 $j$ 的 $c_{ij}$ 的和。计算方法如下：

4的部分容易处理，对于每一个 $i$ 是 $\mathcal{O}(1)$ 计算的。
1的3的部分，可以通过从左到右扫描时，维护一个对于所有 $b_j$ 的值的 $j+1$ 的和来计算。就是下面程序中left[x]和right[x]。 $i$ 从0开始变大的时候，开始left和right逐渐增加，当 $i$ 大于 $n/2$ 之后，又逐渐减少。
2的部分，同样维护一个 $(L,R)$ 之间的所有值的 $b_i$ 的个数， $i$ 小于 $n/2$ 时逐渐减少， $i$ 大于 $n/2$ 后逐渐增多。下面的mid[x]。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[500005], b[500005];
ll left[500005];       // left[x] is the sum of j+1 for all b[j]=x, to the left of i
ll right[500005];      // right[x] is the sum of N-j for all b[j]=x, to the right of N-i
ll mid[500005];
ll ans;
 
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;++i) 
        scanf("%d", &a[i]);
    for(int i=0;i<n;++i) {
        scanf("%d", &b[i]);
        mid[b[i]]++;
    }
    
    for (int i = 0; i < n; i++) {
        int L = min(i, n-i-1), R = max(i, n-i-1);
 
        ans += left[a[i]] + right[a[i]];
        if (a[i] == b[i])
            ans += (ll)i*(i+1)/2 + (ll)(n-1-i)*(n-i)/2;
        ans += mid[a[i]] * (L+1);
 
        if (i+1 <= n-i-2) {         // i and N-i-1 are added
            left[b[i]] += i+1;
            right[b[n-i-1]] += i+1;
            mid[b[i]]--;
            mid[b[n-i-1]]--;
        } else if (i >= n-i-1) {    // N-i-2 and i+1 is removed
            left[b[n-i-2]] -= n-i-1;
            right[b[i+1]] -= n-i-1;
            mid[b[i+1]]++;
            mid[b[n-i-2]]++;
        }
    }
    printf("%lld\n",ans);
 
    return 0;
}