Erisu._.3812's blog

Finding sum
By Erisu._.3812, history, 13 months ago, In English

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)

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply