Subtask 1

For each query, solve the 0-1 knapsack with items between ~l~ and ~r~.

Key Concepts: Dynamic Programming

Time Complexity: ~\mathcal{O}(\max(r-l) \times \max(t) \times Q)~

Subtask 2

Create a segment tree with each node storing the best value in range ~l~ and ~r~ for every time ~t~. Merge the nodes in range during query.

Key Concepts: Segment Tree, Dynamic Programming, Implementation

Time Complexity: ~\mathcal{O}(Qt^2 \times \log N)~

Subtask 3

It is possible to solve all queries from ~l~ to ~r~, ~l \le x \le r~ with 2 dp tables, ~dp1[i][j] =~ maximum value with weight ~j~ in the range ~x+1~ to ~i~, ~dp2[i][j] =~ maximum with weight ~j~ from ~x-i~ to ~x~. This table takes ~\mathcal{O}(w(\max(r)-\min(l)))~ to create. With a query from ~l~ to ~r~, ~\text{ans} = \max(dp2[x-l][j] + dp1[r][w-j])~ for all ~j \le w~. This query takes ~\mathcal{O}(w)~ time.

Split the queries into ~2~ groups: ~r-l \le \sqrt n~, ~r-l > \sqrt n~. Sort both groups by ~l~. Solve the queries with the method above using initially ~x = 0~, until a query is reached where ~l > x~, then set ~x = r~ and repeat until all queries are solved.

Key Concepts: Offline Processing, Square Root Decomposition, Dynamic Programming, Implementation

Time Complexity: ~\mathcal{O}(MN^{1.5} + MQ + Q \log Q)~