I know RMQ normally is solved by some maybe more complicated data structures like segment tree, yet sometime ago I found this paper online: http://www.ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

It shows a way to use two BITs to find the RMQ (though only support point update, not range update).

I have read through the paper several times, I understand how to build the BITs and how to query it, but I totally don't know how to update it. I have post a question on Stack Overflow about this too but seems the answer is not fully convincing.

Therefore I would like to know:

1. Is this method solving RMQ well known & common?
2. How exactly is the update operation be done? I would be appreciate if someone can demonstrate with an update on index 5 (1-based)

After reading the analysis of this problem, I once again think that my concept in probability / excepted value is so bad that I should kill myself.

Here is the link of the problem: Typewriter Monkey

Anyway my problem is about the part of calculating the Expected Number of Bananas (# Occurrence of pattern in the string)

Originally, my thought is the most basic one about Expected Value (which I think it must be correct?):

E(X) = P(Exact 1 banana)*1 + P(Exact 2 bananas)*2 + ...

Then I stop right here and think that, it is too hard for me to find the probability...I cannot count it directly as it will double count a lot, I know no good way to use Inclusion-Exclusion Principle here either...I have no idea.

Then I read the solution and it said:

By linearity of expectation, the expected number of copies is then just P multiplied by the number of places the string can occur, which is S-L+1.

where P is the probability of occurrence of the pattern at a fixed point

Now P is easy to calculate as it does not need to consider any repeating / overlapped cases.

However I cannot understand that why simply P*(S-L+1) would be the answer?

Precisely, how can I deduce that E(X) = P(Exact 1 banana)*1 + P(Exact 2 bananas)*2 + ... = P*(S-L+1)

PS: If anyone can provide any source / tutorial for probability (Programming Contest Oriented is better!), I would be very appreciate that I will send a million "Thank You" messages, separately, to your inbox :)

I have an AC solution with following idea, but I could not proof the correctness myself:

Use all Unmarked vertex to form a "wall" to separate 1 marked vertex V0 and the others, it can always be done as k >= 2 and pre-check k < n (as when k==n, there is no solution obviously)

So now we have 3 set of vertex: {v0}, {unmarked vertex}, {marked vertex \V0}

Link them up using n-1 edge to conserve the "connected graph" property, it can also be done as m >= n-1

I have drawn a picture to illustrate the idea (bare with my MSpaint skill :O) )

for more edges, just link any vertex p,q, except p belongs to {V0} and q belongs to {marked vertex \V0} (or vice versa)

With this method, V0 is always "unseen" to {marked vertex \V0}, which means having INF range

so, for n-1 <= m <= (n-1)(n-2)/2 + (n-k), I can always construct a graph which is the solution,

I claim for (n-1)(n-2)/2 + (n-k) < m <= n(n-1)/2 , there is no solution.

I cannot proof the last claim though...Anyone could help? :(