(Sorry for my poor English… :(

By using the data structure above, you can solve this problem in \(O(N\log N \log \max(A)+Q\log^2\max(A))\).

Consider if among all the queries, \(l=1\) and \(r=N\), the problem can be solved by “Liner Basis”, in \(O(N\log \max (A))\).

Now \(l,r\) are given. It is easy to use a segment tree, range query in \(O(\log N \log^2 \max(A))\) per query (while there’s \(O(\log N)\) different segments, and merging two “Liner Basis” in \(O(\log^2\max(A))\)). However, it’s too slow to get AC. You may get 27*TLE if you simply do this.

By preprocessing carefully, you can speed up it, to \(O(\log N+\log^2\max(A))\).

Since there are \(O(\log N)\) layers in the segment tree, and \(O(N)\) vertexes in all, we can find that if we preprocess every vertex its “Liner Basis”, we can make the \(O(\log N)\) merging into \(O(1)\).

Now imagine you are at a vertex, its index, l, r are known. You can construct the “Liner Basis” from the middle (i.e. \(\dfrac{l+r}{2}\)), to right and to left, twice. After that, every vertex has two “Liner Basis”, one on the left, one on the right.

By doing this, you only need to find one vertex that \([L_i,R_i]\) covers its \(middle\), and merge its left “Liner Basis” and its right “Liner Basis”.

(If you are confused about it, you can go to this blog and learn more about the special kind of segment tree which called “cat tree”)

Now, it can be solved in \(O(N\log N \log \max(A)+Q\log^2\max(A))\).

Since it’s much slower than the standard method, it’s sure that simply coding can lead to many TLEs. Here are three tips for you to speed up your code :)

• When you construct the “Liner Basis” on each vertex, take down something like”insert element, insert index”, instead of copying the “Liner Basis” many times.

• Use fast read instead of “scanf” or “cin”.

• Type “ #pragma GCC optimize(“Ofast”) “ at the beginning of your code.

After this, you can get AC on this problem since there are 3000ms.

code: https://atcoder.jp/contests/abc223/submissions/30582975