You are not logged in. Please login at to post your questions!


SOSTD Editorial




Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi


Segment Tree, Lazy Propagation


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 $$\left(\mathrm{max}*{(p \in S)} \; A_p\right) \cdot \left(\mathrm{max}*{(p \in S)} \; B_p\right) \,.$$

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$


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


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)$


AUTHOR's solution

TESTER's solution

This question is marked "community wiki".

asked 24 Dec '18, 15:47

deadwing97's gravatar image

accept rate: 0%

edited 25 Dec '18, 04:24

admin's gravatar image

0★admin ♦♦

@admin @deadwing97 SL∗L+SL+1∗(L+1)+SL+2∗(L+2)+....++SR∗R <-- why are we doing this ?


answered 27 Jan, 22:02

hedgehog_'s gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 24 Dec '18, 15:47

question was seen: 581 times

last updated: 27 Jan, 22:02