You've learned the Convex Hull Trick:
When DP has linear terms mixing indices, rewrite as .
Each defines a line. You query the lower envelope at .
For sorted queries: total using a deque.
For arbitrary queries: using binary search or Li Chao tree. CHT doesn't need QI. It works on a completely different structure: linearity. You now have another tool for breaking through TLE. For practice, solve the problems in the problemset.