| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Given a list of interval, find the maximum difference between two intervals. The difference between two intervals A and B is the number of element that are in A and not in B, or in B and not in A.
UDP : It mean element that are exactly only in one of A and B
Can it be found in O(n) ?
I fail to see how you could do that in $$$\mathcal{O}(n)$$$ time since, at best, you would likely need to sort your intervals so as to optimise your search/counting. So, at least $$$\mathcal{O}(n\log_2 n)$$$.
I have already resolved intervals using scanline with O(n) complexity, that's why I put O(n), but I am okay with O(nlogn).
It only works when the range of interval endpoints are also $$$\mathcal{O}(n)$$$. Otherwise, there needs to be any kind of sorting that takes at least $$$\mathcal{O}(n\log{n})$$$ before you can start scanning.
Ah yes, you're right.
For any pair of intervals, you can first find the amount of space that is in A and the amount of space that is in B, take the max of those, and subtract off the amount of space that is in both. The max of all pairs should be the answer.
Yes but it will not be O(n^2)?
well what if n is equal to the square of the number of intervals?
No there are no problems, If it's, I want only to know if there is a better algorithm to do it, as you can see in most intervals where brute force idea is O(n^2), but you can actually have O(nlogn). The thing that lead me to that problem is that I was resolving 1834D - Опрос на уроке, and I had done for it a wrong mathematical representation. Before see editorial, I was thinking that the problem can be represented like the difference of two intervals. But actually it is :
A \ ( A n B) and not what I was thinking (A u B) / (A n B)
So the question comes naturally, does the difference can be done in O(nlogn)
Auto comment: topic has been updated by rumike (previous revision, new revision, compare).
You could probably do $$$O(n\log n)$$$ with max fenwick/segment trees. There are 3 kinds of intersections when you fix the rightmost interval:
None — $$$a_l\leq a_r<b_l\leq b_r$$$ difference is $$$a_r-a_l+1+b_r-b_l+1$$$
Partial — $$$a_l<b_l\leq a_r\leq b_r$$$ difference is $$$b_r-a_r+b_l-a_l$$$
Full — $$$b_l\leq a_l\leq a_r\leq b_r$$$ difference is $$$b_r-a_r+a_l-b_l$$$
You can use scanline for 1, and 2 segment trees keeping $$$-a_r-a_l$$$ and $$$a_l-a_r$$$ for 2 and 3 respectively.
From left-to-right in sorted order by the right borders:
Query the first segment tree $$$[l,r]$$$ and add $$$b_r+b_l$$$ to the result
Query the second segment tree $$$[l,r]$$$ and add $$$b_r-b_l$$$ to the result
Update both segment trees at position $$$r$$$
Note that using the first segment tree for 3 or using the second segment tree for 2 does not matter because we are taking the max of all of them.
Thank you so much.
But I don't understand well the querying of segment trees. For example for partial intersection, It is ok to save - ar — al in segment tree before, and during query on range [ bl , br], how to query only intervals a, for which al≤bl<ar≤br is verified.
For partial $$$a_l<b_l\leq a_r\leq b_r$$$, notice that $$$b_r-a_r+b_l-a_l>b_r-a_r+a_l-b_l$$$ and since we are dealing with max the wrong difference will never be chosen.
Got it, thank you.