Non-Cat-Rinks (Shpjegimi i zgjidhjes)

Problem Author:	Kostiantyn Denysov
Prepared by:	Andrii Kholod and Kostiantyn Denysov
Edited by:	Kostiantyn Denysov

A segment $h [l .. r]$ is called good if there exists a tree on the vertices $l, l + 1, \dots, r$ l, l+1, \dots, r such that for each vertex $v$ , the length of the longest simple path passing through $v$ is exactly $h_{v}$ h_v.

In other words, a good segment requires no reductions of $h_{v}$ h_v values — the tree structure alone satisfies all constraints.

Our first goal is to determine necessary and sufficient conditions under which a segment is good.

We now derive basic necessary conditions for a segment $h [l .. r]$ to be good.

Let $k = r - l + 1$ k = r - l + 1 denote the number of vertices in the segment.

Local upper bound. For any vertex $v \in [l, r]$ v \in [l, r], we must have [ h_v k - 1. ] This is because the longest possible simple path in any tree of $k$ nodes has at most $k - 1$ k - 1 edges (i.e., the diameter of the tree).
Multiplicity of the maximum. Let $M = max (h_{l}, h_{l + 1}, \dots, h_{r})$ M = \max(h_l, h_{l+1}, \dots, h_r) be the maximum desired path length in the segment. In a good segment, the tree must have diameter exactly $M$ . Indeed, for any vertex $v$ such that $h_{v} = M$ h_v = M, there must exist a simple path of length $M$ passing through $v$ , and since the diameter is the longest path in the tree, we conclude that the diameter must be equal to $M$ .
As a consequence, we must be able to embed a path of length $M$ in the tree, which requires at least $M + 1$ M + 1 distinct vertices. Moreover, for each such vertex $v$ on the diameter, we must have $h_{v} \geq M$ h_v \ge M, and since $M$ is the maximum, we conclude that:
The number of times $M$ appears in $h [l .. r]$ must be at least $M + 1$ M + 1.
Reachability constraint. Let $m = min (h_{l}, h_{l + 1}, \dots, h_{r})$ m = \min(h_l, h_{l+1}, \dots, h_r). We claim that the diameter $M$ must satisfy
$M \leq 2 \cdot m - 2.$ M \le 2 \cdot m - 2.
In any tree of diameter $M$ , consider the two endpoints of the diameter path. Any other vertex $v$ must be placed somewhere in the tree — and thus its distance to at least one of the two endpoints is at least $⌈ \frac{M}{2} ⌉ + 1.$ \left\lceil \frac{M}{2} \right\rceil+1.
Now, suppose there is a vertex $v$ such that
$h_{v} < ⌈ \frac{M}{2} ⌉ + 1.$ h_v < \left\lceil \frac{M}{2} \right\rceil + 1.
Then, the longest path that goes through $v$ cannot possibly stretch far enough to include both distant ends of the diameter. Hence, the tree cannot satisfy needed condition.

It is not hard to show that these conditions are also sufficient.

In the general case, we are allowed to reduce values of $h_{v}$ h_v at a cost. However, not all reductions are equally useful — and some are outright dangerous.

Let us focus on a key observation:

It is generally undesirable to reduce the minimum value in the segment.

To make a segment $h [l .. r]$ good, we must ensure that all three conditions are satisfied. Let us first focus on conditions (1) and (3), which are purely local and can be enforced in a straightforward way.

Condition 1: For all $v \in [l, r]$ v \in [l, r], we must have $h_{v} \leq k - 1$ h_v \le k - 1, where $k = r - l + 1$ k = r - l + 1.
Condition 3: We must ensure that $min (h_{l}, \dots, h_{r}) \geq ⌈ \frac{M}{2} ⌉ + 1.$ \min(h_l, \dots, h_r) \ge \left\lceil \frac{M}{2} \right\rceil + 1.

However, we do not yet know what the final value of $M$ (i.e., the maximum value after reductions) will be. To ensure both constraints are met, we preemptively cap all values $h_{v}$ h_v using the following formula: $h_{v} := min (h_{v}, k - 1, 2 \cdot min (h_{l}, \dots, h_{r}) - 2) .$ h_v := \min\left(h_v,\; k - 1,\; 2 \cdot \min(h_l, \dots, h_r) - 2\right).

This transformation guarantees that:

No value exceeds the maximum path length in a $k$ -node tree.
The resulting maximum $M$ will not exceed $2 \cdot min - 2$ 2 \cdot \min - 2, thus preserving the reachability constraint.

This normalization step makes it easier to satisfy the third condition regardless of the original values. It also narrows our focus: we now only need to ensure that the capped maximum appears at least $M + 1$ M + 1 times to satisfy condition (2).

To achieve this, we can reduce values $h_{v} > M$ h_v > M down to $M$ at some cost. Our goal is to find the minimal possible cost to satisfy the condition.

This can be done using binary search on $M$ . We iterate over all possible values of $M$ in the range $[min, min \cdot 2 - 2]$ [min, min \cdot 2-2] and check for each $M$ whether we can obtain at least $M + 1$ M + 1 occurrences of $M$ by reducing larger values.

This approach works because the second condition becomes easier to satisfy as $M$ decreases — the set of valid $M$ forms a prefix, so binary search applies naturally.

In our binary search, we are looking for the greatest value of $M$ such that, after reducing all values greater than $M$ to $M$ , the number of values equal to $M$ is at least $M + 1$ M + 1.

This is equivalent to checking whether $cnt := # {v \in [l, r] ∣ h_{v} \geq M} \geq M + 1.$ \text{cnt} := \#\{v \in [l, r] \mid h_v \ge M\} \ge M + 1.

Therefore, during binary search:

If $cnt > M$ \text{cnt} > M, then the condition is satisfied, and we try a bigger $M$ .
If $cnt \leq M$ \text{cnt} \le M, then the condition is not satisfied, and we must try a smaller target — that is, move the binary search to the left.

A naive implementation of the binary search would, for each candidate value $M$ , scan the segment $[l, r]$ [l, r] to count the number of elements $\geq M$ and compute the total cost of reducing them to $M$ . This leads to $O (lo g M)$ O(\log M) iterations, each taking $O (lo g n)$ O(\log n) queries, for a total of $O (lo g M \cdot lo g n)$ O(\log M \cdot \log n) time per query.

To answer each query efficiently, we will build a persistent segment tree that supports range frequency queries.

We construct the tree over the domain of possible $h_{v}$ h_v values (from $2$ to $3 \cdot 1 0^{5}$ 3 \cdot 10^5). Each leaf corresponds to a specific value $x$ , and stores how many times this value appears in the current prefix.

We build one version of the segment tree for each prefix $[1.. i]$ . That is, the $i$ -th version of the tree encodes the frequencies of all values $h_{1}, h_{2}, \dots, h_{i}$ h_1, h_2, \dots, h_i. The transition from version $i - 1$ i - 1 to $i$ consists of a single update: incrementing the count at leaf $h_{i}$ h_i.

Since each update only modifies $O (lo g H)$ O(\log H) nodes, and all other nodes are shared between versions, the total space usage is $O (n lo g H)$ O(n \log H), where $H$ is the maximum possible value of $h_{v}$ h_v.

Given a query for a range $[l, r]$ [l, r], we can access version $r$ and version $l - 1$ l - 1 and compute:

The number of values $\geq M$ in the range is equal to: $count_{\geq M} = query (root_{r}, M, H) - query (root_{l - 1}, M, H) .$ \text{count}_{\ge M} = \text{query}(\text{root}_r, M, H) - \text{query}(\text{root}_{l - 1}, M, H).

Instead of performing a separate binary search over possible values of $M$ , we can integrate the search directly into the structure of the persistent segment tree.

Recall that each node of the segment tree corresponds to a range of values $[x, y]$ of $h_{v}$ h_v. Each internal node has two children covering $[x, m]$ and $[m + 1, y]$ [m+1, y].

At each step, we maintain the current node covering a value range $[x, y]$ , and we want to determine whether the second condition (i.e., at least $M + 1$ M + 1 occurrences of $M$ ) can be satisfied for any $M$ in this range.

Since each node stores the total count of values in its range, we can:

Compare the number of values in the right child (i.e., for values $\geq m + 1$ \ge m + 1) to the candidate threshold,
If the right child contains enough values to satisfy the condition, then the optimal $M$ must lie there — we recurse into the right subtree,
Otherwise, we recurse into the left child.

This process naturally mimics a binary search over values of $M$ , but with the advantage that we avoid duplicate comparisons and reuse precomputed range sums. The optimal $M$ is found in $O (lo g H)$ O(\log H) time by descending once from root to leaf.

Final Complexity

With all optimizations in place, our final solution has the following performance characteristics:

We build a persistent segment tree over the domain of possible $h_{v}$ h_v values. This requires $O (n lo g H)$ O(n \log H) time and memory, where $H$ is the maximum possible value of $h_{v}$ h_v.
Each query is answered in $O (lo g H)$ O(\log H) time by descending once from root to leaf in the persistent tree version corresponding to $r$ and $l - 1$ l - 1.

$Preprocessing: O (n lo g H), Per query: O (lo g H), Total memory: O (n lo g H)$ \boxed{ \text{Preprocessing: } O(n \log H), \quad \text{Per query: } O(\log H), \quad \text{Total memory: } O(n \log H) }

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 3e5 + 11, inf = 1000111222;


struct node {
    int cnt, l, r;
    ll sum, sum_a;

    node() : cnt(0), sum(0), sum_a(0), l(0), r(0) {}
};

node t[max_n * 20];

int h[max_n], a[max_n];


int all = 1;

inline int copy_past (int v) {
    t[all].sum = t[v].sum;
    t[all].sum_a = t[v].sum_a;
    t[all].l = t[v].l;
    t[all].r = t[v].r;
    t[all].cnt = t[v].cnt;
    return all++;
}

inline void upd (int v, int tl, int tr, int pos, int A) {
    ++t[v].cnt;
    t[v].sum += A;
    t[v].sum_a += pos * 1ll * A;
    if (tl == tr) {
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        t[v].l = copy_past(t[v].l);
        upd(t[v].l, tl, tm, pos, A);
    }
    else {
        t[v].r = copy_past(t[v].r);
        upd(t[v].r, tm + 1, tr, pos, A);
    }
}


inline int go (int v1, int v2, int tl, int tr, int cnt = 0) {
    if (tl == tr) {
        return tr;
    }
    int tm = (tl + tr) >> 1;
    if (cnt + t[t[v1].r].cnt - t[t[v2].r].cnt > tm + 1) {
        return go(t[v1].r, t[v2].r, tm + 1, tr, cnt);
    }
    return go(t[v1].l, t[v2].l, tl, tm, cnt + t[t[v1].r].cnt - t[t[v2].r].cnt);
}

inline pair<ll, ll> go_calc (int v1, int v2, int tl, int tr, int pos) {
    if (tl == tr) {
        return {t[v1].sum - t[v2].sum, t[v1].sum_a - t[v2].sum_a};
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        auto res = go_calc(t[v1].l, t[v2].l, tl, tm, pos);
        res.first += t[t[v1].r].sum - t[t[v2].r].sum;
        res.second += t[t[v1].r].sum_a - t[t[v2].r].sum_a;
        return res;
    }
    return go_calc(t[v1].r, t[v2].r, tm + 1, tr, pos);
}



namespace mn_seg {
    struct node {

        int mn;

        /// not existing node
        node () : mn(inf) {}

        node (int x) : mn(x) {
        }
    };



    inline node pull (node a, node b) {
        return node(min(a.mn, b.mn));
    }

    struct segment_tree {
        vector <node> t;
        int n;

        segment_tree () {}

        inline void build (int v, int tl, int tr) {
            if (tl == tr) {
                t[v] = node(h[tr]); /// think
                return;
            }
            int tm = (tl + tr) >> 1;
            build(v << 1, tl, tm);
            build(v << 1 | 1, tm + 1, tr);
            t[v] = pull(t[v << 1], t[v << 1 | 1]);
        }

        segment_tree (int n) : n(n) {
            t.resize(4 * n);
            build(1, 0, n - 1);
        }

        inline void push (int v, int tl, int tr) {

        }

        inline void update (int v, int tl, int tr, int l, int r, int x) { /// think
            push(v, tl, tr);
            if (l > r) return;
            if (tl == l && tr == r) { /// think
                // t[v]
                push(v, tl, tr);
                return;
            }
            int tm = (tl + tr) >> 1;
            update(v << 1, tl, tm, l, min(r, tm), x);
            update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, x);
            t[v] = pull(t[v << 1], t[v << 1 | 1]);
        }

        inline void update1 (int v, int tl, int tr, int pos, int x) { /// think
            push(v, tl, tr);
            if (tl == tr) {
                t[v] = x;
                return;
            }
            int tm = (tl + tr) >> 1;
            if (pos <= tm) {
                update1(v << 1, tl, tm, pos, x);
            }
            else {
                update1(v << 1 | 1, tm + 1, tr, pos, x);
            }
            t[v] = pull(t[v << 1], t[v << 1 | 1]);
        }

        inline node query (int v, int tl, int tr, int l, int r) {
            push(v, tl, tr);
            if (l > r) return node();
            if (tl == l && tr == r) {
                return t[v];
            }
            int tm = (tl + tr) >> 1;
            return pull(query(v << 1, tl, tm, l, min(r, tm)), query(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r));
        }

        inline void upd (int l, int r, int x) {
            update(1, 0, n - 1, l, r, x);
        }

        inline void upd1 (int pos, int x) {
            update1(1, 0, n - 1, pos, x);
        }

        inline node get (int l, int r) {
            return query(1, 0, n - 1, l, r);
        }
    };
}



int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    const int mx = 3e5;

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector <int> roots(n + 1);

    for (int i = 1; i <= n; i++) {
        roots[i] = copy_past(roots[i - 1]);
        upd(roots[i], 2, mx, h[i], a[i]);
    }
    mn_seg::segment_tree T(n + 1);


    for (int it = 0, l, r; it < q; it++) {
        cin >> l >> r;
        int mn_val = min(r - l, T.get(l, r).mn);
        int mx_val = min(r - l, 2 * mn_val - 2);
        int opt = go(roots[r], roots[l - 1], 2, mx);
        umin(opt, mx_val);
        auto res = go_calc(roots[r], roots[l - 1], 2, mx, opt);
        ll ans = res.second - res.first * opt;
        cout << ans << '\n';
    }
}

/*
KoRoVa!
*/

C++