Switches and Payouts

Hard

You get two arrays of the same length n: switches, made of zeros and ones (a switch is off or on), and funds, the money held in each account. Then the queries in queries run in order, each made of three numbers: - [1, l, r]: toggle every switch with index from l to r inclusive, so 0 becomes 1 and 1 becomes 0; - [2, p, 0]: a payout, adding p to every account i whose switch is on; - [3, 0, 0]: report the current total over all accounts. Return the answers to the type 3 queries in the order they appear.

Example 1

switches=[0, 1, 1, 0], funds=[5, 0, 2, 1], queries=[[2, 10, 0], [3, 0, 0], [1, 0, 1], [2, 1, 0], [3, 0, 0]] → [28, 30]

Two switches are on, so a payout of 10 adds 20: 8 + 20 = 28. Then switches 0 and 1 flip, leaving 0 and 2 on, and a payout of 1 adds 2 more: 30.

Example 2

switches=[1, 1], funds=[3, 4], queries=[[1, 0, 1], [2, 100, 0], [3, 0, 0]] → [7]

After the flip every switch is off, so the payout reaches no one and the total stays 7.

Constraints

1 ≤ n ≤ 10⁵
switches[i] is 0 or 1
0 ≤ funds[i] ≤ 10⁹
1 ≤ len(queries) ≤ 10⁵
0 ≤ l ≤ r < n
0 ≤ p ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Segment Tree Array

Similar problems

City Block Outline Hard Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard A Dark Gap Between Street Lamps Hard

Input

switches=[0, 1, 1, 0], funds=[5, 0, 2, 1], queries=[[2, 10, 0], [3, 0, 0], [1, 0, 1], [2, 1, 0], [3, 0, 0]]

Expected

[28, 30]

Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.