Two Characters, Two Colors
Contest: Educational Codeforces Round 157 (Rated for Div. 2)
Difficulty rating: 3100
Tags: binary search, data structures, dp, flows, greedy

You are given a string consisting of characters 0 and/or 1. You have to paint every character of this string into one of two colors, red or blue.

If you paint the $$$i$$$-th character red, you get $$$r_i$$$ coins. If you paint it blue, you get $$$b_i$$$ coins.

After coloring the string, you remove every blue character from it, and count the number of inversions in the resulting string (i. e. the number of pairs of characters such that the left character in the pair is 1, and the right character in the pair is 0). For each inversion, you have to pay $$$1$$$ coin.

What is the maximum number of coins you can earn?

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of four lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the length of the string;
- the second line contains $$$s$$$ — a string of $$$n$$$ characters, where each character is either 0 or 1;
- the third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^{12}$$$);
- the fourth line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$).

Additional constraint on the input: the sum of values of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, print one integer — the maximum number of coins you can earn.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Explanations for the test cases for the example (blue characters are underlined, red ones are not):

1. $$$0100\underline{0}1\underline{0}$$$;
2. $$$10\underline{11}1$$$;
3. $$$\underline{0}1\underline{00000000}$$$;
4. $$$0\underline{1}010000$$$.

Example input:
4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4

Example output:
43
36
76
52

Editorial:
This problem requires partitioning some object into two parts, and imposes different costs depending on how we perform the partition. Let's try to model it with minimum cuts.
Create a flow network with $$$n+2$$$ vertices: a vertex for every character of the string, a source and a sink. Using the edges of the network, we will try to model the following:
• if we paint the $$$i$$$-th character red, we lose $$$b_i$$$ coins (we can treat it as always gaining $$$r_i + b_i$$$ coins no matter what, and then losing coins instead of earning them for coloring the characters);
• if we paint the $$$i$$$-th character blue, we lose $$$r_i$$$ coins (the same applies here);
• if $$$i < j$$$, $$$s_i = 1$$$, $$$s_j = 0$$$ and both $$$s_i$$$ and $$$s_j$$$ are red, we lose $$$1$$$ coin.
To model the third constraint, let's say that the vertices representing $$$1$$$'s are red if they belong to the set $$$S$$$ in the cut, or blue if they belong to $$$T$$$. For the vertices representing $$$0$$$'s, this will be the opposite: they will be red if they belong to the set $$$T$$$, or blue if they belong to the set $$$S$$$. So, if we add a directed edge with capacity $$$1$$$ from $$$i$$$ to $$$j$$$ when $$$s_i = 1$$$, $$$s_j = 0$$$ and $$$i < j$$$, this edge will be cut exactly when both $$$s_i$$$ and $$$s_j$$$ are red, and they create an inversion.
To model the second constraint, for vertices representing $$$1$$$'s, add an incoming edge from the source with capacity $$$r_i$$$, and an outgoing edge to the sink with capacity $$$b_i$$$. For vertices representing $$$0$$$'s, this will be vice versa (since red vertices representing $$$0$$$'s belong to $$$T$$$, the edge from the source to that vertex should have capacity $$$b_i$$$, not $$$r_i$$$).
Now we got ourselves a flow network. The answer to the problem will be $$$\sum\limits_{i=1}^{n} (r_i + b_i) - mincut$$$, where $$$mincut$$$ is the minimum cut in this network. But instead of searching for the minimum cut, we will try to calculate the maximum flow.
We are going to do it greedily. Let's process the vertices of the network, from the vertex representing the $$$1$$$-st character to the vertex representing the $$$n$$$-th character. Every time, we will try to push as much flow as possible through the current vertex.
When processing a vertex, first of all, let's try to push $$$\min(r_i, b_i)$$$ flow through the edges connecting the source and the sink with it. Then, if it is a vertex with a character of type $$$1$$$, let's remember that we can push $$$r_i - \min(r_i, b_i)$$$ flow through it to successive vertices of type $$$0$$$ (let's call this excess flow for that vertex). And if it is a vertex representing a character of type $$$0$$$, let's try to push at most $$$r_i - \min(r_i, b_i)$$$ flow into it from the vertices of type $$$1$$$ we processed earlier (but no more than $$$1$$$ unit of flow from each vertex).
But when we process a vertex of type $$$0$$$, how do we choose from which vertices of type $$$1$$$ we take the flow? It can be shown that we can take $$$1$$$ unit of flow from the vertices with the maximum amount of excess flow (the formal proof is kinda long, but the main idea is that every optimal flow assignment can be transformed into the one working in this greedy way without breaking anything).
So, to recap, when we process a vertex of type $$$1$$$, we remember that it has some excess flow. And when we process a vertex of type $$$0$$$, we take $$$1$$$ unit of excess flow from several vertices with the maximum amount of excess flow. So, we need a data structure that allows us to process the following queries:
• add an integer;
• calculate the number of positive integers in the structure;
• subtract $$$1$$$ from $$$k$$$ maximum integers in the structure.
Model implementation of this data structure is kinda long (there are easier ways to do it), but I will describe it nevertheless. We will use an explicit-key treap which stores two values in each vertex — an integer belonging to the structure and the quantity of that integer in the structure (so, it's kinda like a map which counts the number of occurrences of each integer). This treap has to support adding $$$-1$$$ to all values in some subtree (with lazy propagation). Most operations with it are fairly straightforward, but how do we actually subtract $$$1$$$ from $$$k$$$ maximum values in the tree? We will do it in the following way:
• split the treap to extract $$$k$$$ maximum elements (let's denote the first treap as the part without $$$k$$$ maximums, and the second treap as the part with those $$$k$$$ maximums);
• add $$$-1$$$ to the values in the second treap;
• while the minimum element in the second treap is not greater than the maximum element in the first treap, remove the minimum from the second treap and insert it into the first treap;
• merge the treaps.
It's quite easy to see that if you store the pairs of the form "element, the number of its occurrences" in the treap, the third step will require moving at most $$$2$$$ elements. And the resulting complexity of every operation with this data structure becomes $$$O(\log n)$$$, so the whole solution works in $$$O(n \log n)$$$.