960. Flip and Sum Queries
A row of n lamps is described by two arrays of equal length. a[i] is 1 when lamp i is lit and 0 when it is dark, and b[i] is the energy stored in that lamp. Operations come as triples [t, u, v] in queries, applied in order:
Type 1 [1, l, r] switches every lamp at positions l..r (0-indexed, inclusive): lit becomes dark and dark becomes lit. Type 2 [2, p, 0] charges every lamp that is lit at that moment: b[i] grows by p. Type 3 [3, 0, 0] asks for the total of all b[i] right now. Return the answers to the type 3 operations, in order, as an array of longs (empty if there are none).
Example 1
- Input:
- a = [1,0,1,0]b = [5,5,5,5]queries = [[3,0,0],[2,4,0],[3,0,0],[1,0,3],[2,1,0],[3,0,0]]
- Output:
- [20,28,30]
- Explanation:
The first total is 20. Two lamps are lit, so adding 4 gives 28. After toggling everything the other two lamps are lit; adding 1 gives 30.
Example 2
- Input:
- a = [0,0,0]b = [1,2,3]queries = [[2,9,0],[3,0,0],[1,1,1],[2,2,0],[3,0,0]]
- Output:
- [6,8]
- Explanation:
No lamp is lit at first, so the first add changes nothing (total 6). Toggling lamp 1 and adding 2 raises the total to 8.
Example 3
- Input:
- a = [1]b = [0]queries = [[2,7,0],[2,7,0],[1,0,0],[2,7,0],[3,0,0]]
- Output:
- [14]
- Explanation:
The single lamp is lit for the first two adds (14 in total) and dark for the third, so the final total is 14.
Constraints
- 1 ≤ n = a.length = b.length ≤ 105
- 1 ≤ queries.length ≤ 105
- a[i] is 0 or 1; 0 ≤ b[i] ≤ 104
- For type 1: 0 ≤ l ≤ r < n; for type 2: 0 ≤ p ≤ 104
- Totals fit in a 64-bit integer (at most about 1014)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n + q log n)
- Space
- O(n)