Hello there
I'm trying to solve this problem but i can't seem to find the proper approach
I wasn't able to see the editorial's point of view either
if someone would kindly help me find a way to solve it that would be really appreciated!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello there
I'm trying to solve this problem but i can't seem to find the proper approach
I wasn't able to see the editorial's point of view either
if someone would kindly help me find a way to solve it that would be really appreciated!
Name |
---|
You need to maintain two structures.
First one will simply store all intervals which are painted by same color. (Initially we have N such intervals)
Second structure will actually be simple segment tree with two operations:
Add on an interval
Get sum on an interval
When you need to process second type of queries, you simply ask the sum on an interval from your segment tree. This will work in per query
When you need to deal with first type, you iterate over all intervals these intersect with query's left and right border and add on an interval of segment tree, and replace these intervals with new color.
The trick is in that this process won't take O(N2) as you could initially think, this will work in because on each query of this type we either delete some intervals or add not more than two of them.