×

# MANYLIST - Editorial

Author: Sergey Kulik
Tester: Yanpei Liu
Editorialist: Pawel Kacprzak

Hard

# PREREQUISITES:

Segment tree, sets

# PROBLEM:

Your task is to maintain a list of sets of integers numbered from $1$ to $N$. All sets are initially empty. You have to handle $M$ operations, each of one of the following two types:

1. $\texttt{INSERT(L, R, X)}$: inserts integer $X$ to all sets numbered from $L$ to $R$
2. $\texttt{QUERY(Q)}$: outputs the size of the set numbered $Q$

# QUICK EXPLANATION:

For a partial credit, you can pretty easy use the most straightforward approach by just following the process described in the statement. In order to get full credit, for each inserted element $e$, you can use set data structure to store the ranges of sets having $e$. In order to get the number of elements in each set, you can use segment / interval tree to maintain these values.

# EXPLANATION:

## Simple solution

If $N$ and $M$ are quite small, like in the first two subtasks, where $N, M \leq 1000$, the problem is very easy to solve.

We can store an array $A$ of $N$ sets, where $A[i]$ represents a set numbered $i$. Since all integers, which can be inserted to sets are within the range $[1..N]$, we can store each set as an array, i.e. $A[i][j] = 1$ if and only if integer $j$ is in the set numbered $i$.

In order to handle a single insert operation, we can iterate through sets numbered from $L$ to $R$, and insert the requested $X$ into all of them. This operation takes $O(N)$ time.

Handling a query operation is obvious, we just count the number of $1$'s in the array representation of the requested set.

Since there are $M$ operations to perform, we can achieve $O(N \cdot M)$ time complexity to handle all of them.

The total time complexity of this method is $O(N^2 + N \cdot M)$.

## Faster solution

However the above method is sufficient for small inputs, we need a better one to get a full credit here.

Rather than storying, for a fixed set, the information what elements are in this set, we can think the other way around.

Let $S[e]$ be the ordered list of disjoint ranges of sets having element $e$. For example, if a range $[L, R]$ is in $S[e]$, it means that $e$ belongs to all sets numbered from $L$ to $R$. We say that a range $[A, B]$ is before a range $[C, D$] in our order if and only if $A < C$ or $A = C$ and $B < D$. The disjoint property is very important in the definition, we will use it as the invariant. We are going to implement $S[e]$ as a balanced binary tree in order to be able to handle insert queries. If you are using for example $\texttt{C++}$ you can use $\texttt{std::set< pair < int, int > >}$ to implement a single $S[e]$.

The second data structure that we are going to use is a segment tree $T$. In this tree, we will store the information on how many elements are in sets numbered from some $L$ to $R$. We will use it to update the number of elements in a range of sets and to get the number of elements in a particular set.

Initially, both structures are empty. This means that $S[e]$ is empty for all valid $e$ and all nodes in $T$ are initialized to have $0$ elements.

Now, we are going to describe, how we handle both operations. We will start with insert, because it exposes the nature of the problem in a great manner.

### Insert operation

Suppose that we are going to insert element $X$ to all sets numbered from $L$ to $R$. The idea of the solution is to find in $S[X]$ the set $Y$ of all overlaping ranges with $[L, R]$. After inserting $X$ to sets numbered from $L$ to $R$, all sets in a range $Y \bigcup [L, R]$ will have element $X$. What we are going to do, is to replace all ranges from $Y$ in $S[X]$ with a single range representing the just mentioned sum of ranges.

In order to do that, for which range $A \in Y$, we decrease the number of elements in a range $A \bigcap [L, R]$ by one, and delete $A$ from $S[X]$. At the end, we increase the number of elements in $[L, R]$ by one, and we insert the range $Y \bigcup [L, R]$ to $S[X]$. Notice that we maintain the number of elements of sets in a range using our segment tree $T$.

Let's now explain some details on how to implement the logic described above.

In order to get the set $Y$, first we find in $S[X]$ the leftmost range of sets which overlaps with $[L, R]$. Do you remember that we implemented $S[X]$ as a balanced binary tree and that all ranges in that tree are disjoint? Based on these two facts, we can quickly find the leftmost range which overlaps with $[L, R]$, in $\texttt{C++}$ you can use $\texttt{lower\_bound}$ method of $\texttt{std::set}$ to achieve that. After that, we can iterate over all ranges overlapping with $[L, R]$ using $\texttt{successor}$ operation on $S[X]$.

All operations of increasing and decreasing the number of elements in sets of a given range are implemented on segment tree in a standard way.

You may wonder what is the complexity of the insert operation. Well, you can notice that each segment is inserted exactly once and erased at most once. Since a single insert / delete / lower_bound / successor operation on $S[X]$ takes $O(\log(n))$ time and update operation on $T$ also takes $O(\log(N))$ time, a single insert operation has $O(\log(N))$ time complexity.

### Query operation

Now, the easier operation, we want to know, how many elements are in the set numbered $Q$. Because we maintain our segment tree $T$, we can answer each such query in $O(\log(N))$ time easily by summing up accumulated values at the path form a leaf corresponding to the set $Q$ to the root of $T$.

### Time complexity

The total time complexity of this solution is $O(N + M \cdot \log(N))$ and this is a very nice speed up over the simple solution.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

# RELATED PROBLEMS:

This question is marked "community wiki".

75485097
accept rate: 12%

19.8k350498541

 1 answered 27 Sep '15, 14:58 11●2 accept rate: 0%
 0 author's and tester's solution are not of this problem :/ answered 27 Sep '15, 14:08 1 accept rate: 0%
 0 Can't understand the insertion part properly. If anyone explain this part, it will be a great help. answered 27 Sep '15, 19:58 1 accept rate: 0%
 0 The practice link and the contest link are of different problem answered 29 Sep '15, 12:31 893●2●11●35 accept rate: 10%
 0 I think for the first two subtask...we can have a sum[] array ..we increment the sum[i] if j th element is newly added to the i th set...by this we reduce the query operation from O(n*n) to O(1) answered 30 Sep '15, 11:25 1 accept rate: 0% You probably mean to reduce a single query time from O(n) to O(1), if so, you are right, but a single update still takes O(n) it this method, so this is not so much improvement. I had considered describing this method in the editorial, but since it doesn't improve the total complexity, I didn't do that. (30 Sep '15, 12:25)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,875
×1,768
×1,359
×163
×35

question asked: 27 Sep '15, 07:37

question was seen: 3,437 times

last updated: 30 Sep '15, 12:25