Recently, in order the celebrate the new year :), I was looking at some codeforces problems. I found one specific data structure problem (here) to be very interesting. I found a blog where much of this problem was explained (as there is no editorial..) but I was wondering if anyone could elaborate on how the blog writer used segment tree to solve this problem.. I could not figure that part out.

Any ideas?

I've used a segment tree to handle following queries:

1. modify (l, r, x) : for each l <= i < r, a[i] = x

2. get (i) : return a[i]

Look at my code : 7839071

Tell me, if you didn't understand some part of it!

I see that, somehow, you are greedily pushing numbers into the answer vector, once you arrive at the indice i. Why is that optimal?

You can prove this using induction on n.

Consider any optimal sequence

b_{1},b_{2}, ...,b_{4k}.If my output is

m_{1},m_{2}, ...,m_{4k}', obviously ifk≥ 1, thenk' ≥ 1 (Because I'll findb_{1},b_{2},b_{3},b_{4}greedily!)Induction step: My solution has guaranteed that

position_{m}_{4}≤position_{b}_{4}. By induction hypothesis, my solution will find an answer with length equal to 4k- 4 for the rest of the array (a_{positionm4 + 1},a_{positionm4 + 2}, ...,a_{n}) and by adding them afterm_{1},m_{2},m_{3},m_{4}, we have an answer of length equal to 4k!(Sorry for my bad English ... Tell me if it's unclear!)

Ok, this is clear now. Can you explain how you are using the "modify" and "get" commands to match numbers between the indice i and the next occurrence of i. To elaborate on this question:

Say you have numbers:

1 2 1 3 2, and we are at indice 1, and obviously next[arr[i]] is indice 3. How do you match the middle 2, at indice 2, to the outer 2 at indice 5?

We'll have another array s.

When we're at indice 1, we won't do anything because it's the first occurrence of 1.

(Also indice 2 is the same)

When we're at the indice 3, we modify s[2] = 1 (We modify the segment between last occurrence of a[i] and i to a[i])

So when we're at the indice 5, we'll have a look at the last occurrence of a[i]! In this case, s[last[a[5]] = 1. So we know the last 2 is surrounded by two '1's and we found

`1 2 1 2`

.Ahhh I finally got it :). Thank you so much. May I ask, what was the motivation behind that solution?

I'm glad that it helped. :)

First of all I tried to find some subsequence of the input (Not the largest one) that satisfies the given conditions. During that process, the greedy solution comes in my mind and then the the only problem was "how to find the first

ababfast?". After that I used some kind ofdfsto find the idea and it just worked well!"My solution has guaranteed that positionm4 ≤ positionb4" could you explain this part more clearly? I mean, I understood the line before this, that is if k>= 1, then k' ≥ 1-but don't get how this leads to the conclusion that position of m4 <= position of b4