Overview

By defining the value of each bookshelf \(i\) as \(A_i \times V_i\), the problem asks us to find, for each query, “the sum of values of bookshelves within the interval \([L_j, R_j]\) that satisfy \(D_i \leq T_j\).”

We efficiently compute interval sums considering only bookshelves that have been repaired by date \(T_j\).

Analysis

The value we want to find for each plan \(j\) is:

\[ \sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i \]

For bookshelf \(i\), the rental fee obtained is always \(A_i \times V_i\).
Therefore, we consider each bookshelf as follows:

• Position: \(i\)
• Activation date: \(D_i\)
• Value: \(A_i \times V_i\)

For each query, we need to find the sum of bookshelves that “became active by date \(T_j\)” and whose position is within \([L_j, R_j]\).

Naively checking from \(L_j\) to \(R_j\) for each query takes \(O(NQ)\) in the worst case.
Since \(N+Q \leq 2 \times 10^5\), this is too slow.

Instead, we process queries in ascending order of date \(T_j\).

When processing queries from smallest date first, the set of target bookshelves only grows incrementally.
In other words, if we add bookshelves in ascending order of repair completion date \(D_i\), each bookshelf only needs to be processed once.

For the added bookshelves, if we place the value \(A_i \times V_i\) at position \(i\), each query can be answered as an interval sum:

\[ \text{sum}(L_j, R_j) \]

To efficiently compute interval sums, we use a Fenwick Tree (BIT).

Algorithm

We process as follows:

1. For each bookshelf, create the following information:

   • Repair completion date \(D_i\)
   • Position \(i\)
   • Value \(A_i \times V_i\)

2. Sort bookshelves in ascending order of \(D_i\)

3. For each query, create the following information:

   • Date \(T_j\)
   • Interval \([L_j, R_j]\)
   • Query number \(j\)

4. Sort queries in ascending order of \(T_j\)

5. Prepare a Fenwick Tree
   We will add “values of bookshelves repaired up to the current date” to the Fenwick Tree by position

6. Process sorted queries in order:

   • Let the current query’s date be \(T\)
   • Add all bookshelves with \(D_i \leq T\) to the Fenwick Tree
   • Compute the sum over interval \([L, R]\) using the Fenwick Tree
   • Store the answer at the position corresponding to the original query number

In the Fenwick Tree, the interval sum is computed as:

\[ \text{sum}(L, R) = \text{prefix\_sum}(R) - \text{prefix\_sum}(L-1) \]

For example, when processing a query with date \(T=5\), only bookshelves with \(D_i \leq 5\) have been added to the Fenwick Tree.
Taking the interval sum in this state gives us the total of only the bookshelves that satisfy the condition.

Complexity

• Time complexity: \(O((N+Q)\log N)\)
  • Sorting bookshelves: \(O(N\log N)\)
  • Sorting queries: \(O(Q\log Q)\)
  • Each bookshelf addition and each query’s interval sum retrieval: \(O(\log N)\) each
• Space complexity: \(O(N+Q)\)

Implementation Notes

• Queries are sorted in ascending order of \(T_j\) for processing, but output must be in input order.
  Therefore, we keep the query number qi together and store the answer in ans[qi].

• Implementing the Fenwick Tree as 1-indexed is convenient since bookshelf numbers from \(1\) to \(N\) can be used directly.

• When adding bookshelves, since the condition is \(D_i \leq T_j\), we use while items[p][0] <= t:.
  Note that we include the equality because bookshelves become available for lending starting from day \(D_i\).

• The answer can be as large as \(2 \times 10^{13}\), so in other languages, a 64-bit integer type is necessary. In Python, the standard int handles this without issues.

  Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
idx = 0

N = data[idx]
Q = data[idx + 1]
idx += 2

items = []
for i in range(1, N + 1):
    a = data[idx]
    d = data[idx + 1]
    v = data[idx + 2]
    idx += 3
    items.append((d, i, a * v))

queries = []
for qi in range(Q):
    l = data[idx]
    r = data[idx + 1]
    t = data[idx + 2]
    idx += 3
    queries.append((t, l, r, qi))

items.sort()
queries.sort()

bit = [0] * (N + 1)

def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i

def prefix_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

ans = [0] * Q
p = 0

for t, l, r, qi in queries:
    while p < N and items[p][0] <= t:
        _, pos, val = items[p]
        add(pos, val)
        p += 1
    ans[qi] = prefix_sum(r) - prefix_sum(l - 1)

print("\n".join(map(str, ans)))

---

This editorial was generated by gpt-5.5-high.