Розбір

Let us iterate through the difference between $l_1$ and $l_2$, which can range from $-n$ to $n$. We will shift the array $b$ by this difference. Now, the problem reduces to: given two arrays $a$ and $b$, count the number of segments $[l,r]$ such that

We create an array $t$ such that $t_i=f(a_i-b_i)$. This simplifies the problem further to counting the number of segments $[l,r]$ such that

We construct a prefix sum array $p$, where

This allows us to rewrite the sum over the segment $[l,r]$ as $p_{r+1}-p_l$

Now, we iterate over the right boundary $r$ of the segment. The problem is reduced to counting the number of indices $j\le r$ such that $p_j=p_{r+1}$. This can be done in several ways, for example, by maintaining an array $k$, where $k_i$ represents the count of prefix sums equal to $i$.

Time complexity: $O(n^2)$ or $O(n^2\cdot log(n))$

Memory complexity: $O(n)$

#define int long long

int log_ = 25;
long long inf = 800000007ll;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> b(n);
    for (int i = 0; i < n; i++)
        cin >> b[i];
    int ans = 0;
    for (int sd = -n; sd <= n; sd++) {
        vector<int> col(2 * n + 5);
        int p = n;
        col[p]++;
        for (int i = 0; i < n; i++) {
            int j = i + sd;
            if ((j < 0) or (j >= n))
                continue;
            if (a[i] < b[j])
                p++;
            if (a[i] > b[j])
                p--;
            ans += col[p];
            col[p]++;
        }
    }
    cout << ans;
}