Map update intervals to points $$$(L, R)$$$ on the plane with weight $$$R - L$$$. Queries are the maximum weight of a point in the square with corners $$$(L, L), (R, R)$$$. You can do polylog with any of your favorite data structures like 2D segtree, segtree of BBST and whatnot.

Online, $$$l_i, r_i \leq 10^9$$$:

Use a sparse segment tree with a sparse BIT in each node. In the segment tree, the node representing range $$$[L, R]$$$ contains all intervals $$$i$$$ such that $$$l_i \in [L, R]$$$. In the BIT, the value of the element at index $$$r_i$$$ is $$$r_i - l_i + 1$$$.

This reduces the problem to:

1. Given an index $$$r$$$, find the maximum element in $$$[0, r]$$$.
2. Given an index $$$r$$$ and value $$$v$$$, set the value of the element at index $$$r$$$ to $$$\max(value, v)$$$.

This is easily solvable with a BIT. Complexity: $$$O(Q \log^2 (10^9))$$$ with a high constant factor.

There exists a general offline approach, when you have inserts in a set and queries that are cumulative and you can easily solve the problem if all inserts were before the queries.

Lets say the operations are stored in an array $$$\mathtt{op[1\ldots Q]}$$$. Then use this divide and conquer approach --

solve(l, r): 
  if l == r: return
  m = (l + r) / 2
  inserts = inserts in op[l..m]
  queries = queries in op[m+1..r] 
  updateAnswer(inserts, queries) 
  solve(l, m)
  solve(m + 1, r)

If you call $$$\mathtt{solve(1, Q)}$$$, you'll see that for every query this divide and conquer approach will consider every updates before it. If the objective function is cumulative then updating answer for each chunk will result in correct answer.

In your problem, the $$$\mathtt{updateAnswer}$$$ part can be done by line sweep; by sorting both the inserts and the queries by one end point and keeping a Binary Indexed tree on the other end point. This will result in $$$O(Q\log Q)$$$ for each recursion depth. So in total $$$O(Q \log^2 Q)$$$.

For other uses of this approach see the sections of CDQ Divide and Conquer from this slide: https://assets.hkoi.org/training2018/dc.pdf

To get a single log, I remember keywords like fractional cascading and interval tree (not segment tree). Does somebody confirm that it's one of these two? :D

There is also a technique to expand a static queryable Data Structure in O(log n) Amortised Complexity per query. Just maintain a Static Data structure in sizes of 2^i. On adding, Keep merging into the smallest set unless all are again size of 2^i. Find the best on all log(n) sets separately. You can use any of the online/offline approaches of the second part with just a log(n) extra in the complexity.

Never mind