Dragons#11766

Dragons (Анализа на решението)

Problem Author:	Illia Shevchenko
Prepared by:	Maksym Shvedchenko Illia Shevchenko
Editorial by:	Maksym Shvedchenko

Let us iterate through the difference between $l_{1}$ l_1 and $l_{2}$ 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]$ [l, r] such that

i = l \sum r f (a_{i} - b_{i}) = 0.

\sum_{i=l}^{r} f(a_i - b_i) = 0.

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

i = l \sum r t_{i} = 0.

\sum_{i=l}^{r} t_i = 0.

We construct a prefix sum array $p$ , where

p_{i} = j = 1 \sum i - 1 t_{j} .

p_i = \sum_{j=1}^{i-1} t_j.

This allows us to rewrite the sum over the segment $[l, r]$ [l, r] as $p_{r + 1} - p_{l}$ 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 \leq r$ j \leq r such that $p_{j} = p_{r + 1}$ p_j = p_{r+1}. This can be done in several ways, for example, by maintaining an array $k$ , where $k_{i}$ k_i represents the count of prefix sums equal to $i$ .

Time complexity: $O (n^{2})$ O(n^2) or $O (n^{2} \cdot l o g (n))$ 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;
}