PROBLEM LINK:
Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi
PREREQUISITES:
Segment Tree, Lazy Propagation
PROBLEM:
You are given two integer sequences A_1, A_2, A_3, \ldots, A_N and B_1, B_2, B_3, \ldots, B_N.
Consider an arbitrary non-empty subset S of the set \{1, 2, \ldots, N\}. Let’s define the swagness of such a set as
Hussain is interested in the sum of swagnesses of all possible sets S. (Note that there are 2^N-1 such sets.) Since the sum may be very large, compute it modulo 10^9+7.
1 \leq N \leq 10^5
EXPLANATION:
Let’s maintain an array of pairs P[1...N] such that P_i = (A_i,B_i)
First of all, let’s sort our pairs according to A. Let’s iterate through the pairs one by one. Suppose we are processing the i^{th} pair P_i. Let’s think how this pair contributes to the final answer.
If our pairs are sorted then clearly A_i would be the maximum A for any subset of the set containing the first i elements (but must contain the i_{th} one for sure). So we will have A_i included in 2^{i-1} multiplicands (and all of them are added to the final answer). So now we got rid of one part of the problem. We still have B coefficients.
Let’s maintain a segment tree with MaxV=10^6 leaves (or you can compress numbers and have N leaves but such a thing is not necessary). In the i^{th} leave we record 2 values (consider leaves from left to right).
The first value is S_i the number of subsets having max_B = i
The second Tot_i is simply i*S (we will see why we need it).
So a node covering [L,R] in the segment tree will have S equal to the number of subsets such that max_B \in [L,R].
For this node Tot will be equal to S_L*L \, + S_{L+1}*(L+1) \,+ S_{L+2}*(L+2) \, + .... + \, + S_{R}*R
In other words Tot = Tot_L+Tot_{L+1}+.....+Tot_R
Now let’s get back. Consider the i_{th} pair. For all subsets having max_B \leq B_i we can add our pair to these subsets and the swagness of all of them (after adding our pair) will be A_i*B_i. Counting the number of subsets is just an interval sum query on the segment tree since we are recording the number of subsets for each interval. Let’s denote this sum by LessSubCount.
Now what about the other case, if max_B>B_i ? We will have something like
A_i*{y_1}*S_{y_1}+A_i*y_2*S_{y_2}...
Where y_k is some value (representing some B coefficient) and y_k>B_i.
S_{y_k} denotes the number of subsets such that max_B=y_k. Take A_i as a common factor so we have A_i*({y_1}*S_{y_1}+{y_2}*S_{y_2}+....).
Doesn’t this look familiar? Well, it’s the sum of Tot values. So basically we just need to calculate the sum of Tot values over the interval [B+1, MaxV]. That’s it, we can calculate the contribution of our current pair assuming the segment tree contains correct values.
Now how we should update our segment tree?
When processing a new pair (A_i,B_i) we should add all the subsets containing this pair to our segment tree. Above we calculated the number of subsets which will have max_b=B_i and we denoted it by LessSubCount. Let’s add this value to the number of subsets residing in the B_{i_{th}} leaf.
For all subsets which have max_B>B_i their number (count) is multiplied by 2, because for each one we can add our pair and still the value of max_B won’t change. So our segment tree should support the opreation of multiplying a range by 2. This is a straightforward application of lazy propagation. If you are not familiar with the latter technique you should read about it as I won’t be covering it. Supporting multiplying a range by 2 is no harder at all than supporting adding a number to a range (which is the most basic application of lazy propagation).
A thing also that you should take care about, is resetting the segment tree after each test case. Resetting the whole segment tree is time-consuming. Each update and sum query runs in O(log \, MaxV). Each update modifies log\,MaxV nodes. So after each test case we will have only N*log\,MaxV nodes to reset.
Again, as I said we can compress the numbers and have N leaves only in our segment tree.
Complexity : O(N*log\,MaxV) OR O(N\, log \, N)