Description

Given $n$ pairs $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$.

There are $q$ queries $(l, r)$. For each query, initialize an array $a$ of length $n$ with all zeros. For each $i$ such that $l \le i \le r$, add $y_i$ to $a_1 \sim a_{x_i}$. Find $\max_{i=1}^n a_i$ after all operations.

Limitations

$1 \le n, q \le 5 \times 10^5$

$1 \le x_i \le n, |y_i| \le n$

Time limit : $10$ seconds

Memory limit : $1024$ MB

Solution

Transform the operations into point additions and find the maximum suffix sum.

Note that since the initial values are zero, and the problem does not specify taking the maximum with zero, we need to extract global operations, use prefix sums for preprocessing, and calculate each query separately.

In array $a$, only the positions that are modified matter. Therefore, sort the pairs in ascending order of $x_i$, and for pairs with the same $x_i$, sort in descending order of $y_i$ (to ensure that all operations for the same $x_i$ are taken into account).

Let $p_i$ denote the original index of the $i$-th pair after sorting. Then each query asks for:

$$\max\left(0, \max_{i=1}^n \sum_{j=i}^n y_j \times [l \le p_j \le r]\right)$$

Applying the approach from D2T2 directly: divide the pairs into blocks with size $B=\sqrt n$, perform $O(B^2)$ divide-and-conquer preprocessing for each block, and merge the answers from each block for queries. The time complexity is $O(n\sqrt n)$.