Consider this case,A[7 8 9 4 5 6]， B[3]，the leftmost element is 7，but you need to insert 3 after 4， not after 7. Also, the nlogn solution gives you same result in each step as n^2 solution, not only the final lis length. You can find this point by comparing these two solutions in each step.

Great idea, but it needs to be fixed. Consider this case: A:2 2 3 4 B:1 if you insert 1 after the first 2，the result will not be best. About your question, simple dp runs in O(n^2) and there exists a binary search trick to make it O(nlogn) .

No need to run a multisource BFS, because we have 256 different initial states a0,a1...a255, and for each node x can be reached by at most one initial state. So BFS 256 times is also correct in complexity.

It's quite interesting, and I figured out only when min(u,v)==gcd(u,v) can edge(u,v) be useful. So the number of edges is not big.

Hello!

The same character can appear many times and make many sub-strings whose answer for the 2nd query is 2. So your number of 1st query may be very large.