The problem is to process Q queries of the form X on N pairs of integers a[i] and b[i] (N, Q <= 2e5 and a[i], b[i] <= 1e6).
Assume there is a pointer initially pointing to a[i] or b[i]. For each query, if the number being pointed to is less than X, the pointer switches between a[i] and b[i]. For each query X, find the sum of the entire N-array based on the value pointed to by the pointer. Calculate the sum of all numbers in all configurations after going through Q queries.
Example input: 5 3
10 20
15 25
5 3
7 12
1 4
5
25
8
Output: 168 Explanation: (10+15+5+7+4) + (20+25+3+12+1) + (20+25+5+12+4)
The order doesn't matter right? If that is the case: we can sort it like this:
1 4
5 3
7 12
10 20
15 25
preproccess the prefix sum and suffix sum, then you could find it easily by let us say: x=8
we can simply take the backpart of x<8 (4+3+12)+ (numbers>=8) (10+15) then we could find the position where x<8 using upper_bound, lower_bound or binary search depending on your own implementation
but how are you gonna left the pointers still locate at its current position after, supposing: 6 queries. and also suppose that x = 100, you still have to change the pointer from b to a cause b is smaller than x
Ohh, i get your question now. It was a bit unlcear. I think the answer would be something like maintain a lazy segment tree to calculate how many times a pair has changed, but implementation is pretty hard (for a non-tree & graph person like me). But I think that is the solution for it.