算法1

(暴力枚举) $O(n^2)$

暴力枚举的优化
直接暴力枚举会超时，传统方法是从1-n，2-n，3-n，遍历然后每次向l++，r–，向内计算l-r的交换相等的值，但是一定会超时。观察发现每次向内交换其实会重复，比如，对于16（l，r）和25，向内交换比较从2-5，3-4，2-2都会重复，而且重复交换会随着i的增大增加，想要优化也很简单，就是向外交换，知道2-5的ans一定知道1-6的值等于ans + 1和6交换相等的个数。
关键在于如何遍历可以向外交换找到所有的lr值，观察发现所有的lr向内交换最后的lr无非是相等或者l+1 = r，所以只要将ll，l, l + 1,遍历再找就会找到所有的lr。而且没有重复。

之前做过类似的题，但是思路记住了代码忘了，依稀记得原来的代码简单，但是应该我这种方法时间复杂度比较少吧

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 7501;
int n, a[N], b[N];
int main(){
    cin>>n;
    int res[N];

    int d[N];
    d[0] = 0;
    memset(d, 0, sizeof d);
    for(int i = 1; i <= n; i ++) cin>>a[i];
    for(int i = 1; i <= n; i ++){
        cin>>b[i];
        if(a[i] == b[i]) d[i] += d[i - 1] + 1;
        else d[i] += d[i - 1];
    }

    for(int l = 1; l <= n; l ++ ){
        for(int r = l; r <= l + 1; r ++){
            int li = l, ri = r;
            int ans = 0;

            while(li >= 1 && ri <= n){
                if(li == ri && a[li] == b[li]) {
                    ans ++;

                    res[ans + (d[li - 1] + d[n] - d[ri])] ++;

                    li --, ri ++ ;
                    continue;
                }

                if(a[ri] == b[li]) ans ++;
                if(a[li] == b[ri]) ans ++;

                res[ans + (d[li - 1] + d[n] - d[ri])] ++;

                li --, ri ++;
            }


        }    
    }

    for(int i = 0; i <= n; i ++){
        cout<<res[i]<<endl;
    }



}