I think it is a insanely hard and interesting problem(at least to me),if I'm not miss something: I

have came up with a idea of complexity O(m*sqrt(n)*log(n)*log(answer))

this is my anlanysis:

we want to find the maximum almost everage number between [a,b] in the

interval (L,R), if the answer >=0 ,then we can conclude the length of the

length of [a,b] is either 2 or 3,so we just need to build a segment tree

record maximum (ai+a(i+1)+a(i+2))/2 and (ai+ai+1). if the result of query of [L,R] is non-negative ,then this is the answer, but if it is negative,then

it is more and more complex: we need to binary search the answer x. we need

to check if there is almost average number >=x. we just need to check if there is

[a,b] v[a]-x+v[a+1]-x+...+v[b]-x>=-x , right part is positive. if we split

the interval into two part and have already checked left part and right part

both are <-x,then we need to check the maximum sum of v[i]-x of the suffix

of left part of interval and maximum sum of v[i]-x of prefix of right part

of interval,and check the sum of suffix and prefix.but how to find them

efficiently. we can obersive we need to check prefix and suffix if and only

if the both of the sum of them are positive,that is to say the the slope

suffix sum of left part (i.e. (v[i+1]+..+v[j])/(j-i))>x i.e. (sum[j]-sum[i])/(j-i) and the slope prefix sum of right part >x, so we just need to find a data

structure to record all the suffix convex hull(decreasing index and

decreasing slope) of and interval and all the prefix convex hull(increasing

index and decreasing slope) of interval(of course we also need to know the

convexhull of whole interval),if we know the covexhull, we just need to use

binary search to find the position of slope that is closest to x(after this position,slope of sum <x i.e.sum of v[i]-x is negative just abandon them). the data

structure to preserve the prefix and suffix of convexhull, squarelist is what I can

think of.because this problem denied any off-line approach.we need to build

static squarlist. and for each squarelist we need to record the almost

average number(brute force to find) of this interval and all the prefix and

suffix convexhull of this interval. the whole process of build squarelist is N*sqrt(N). then for each query, if split the query inteval in to O(sqrt(N))interval for each interval that is not cover the whole of one sqarelist,just brute

force to find the value,and maximum sum of v[i]-x,if it is cover the

sqarelist then find the position of prefix covexhull whose slope closest to

x and the position of suffix convexhull of previous squarelist,sum it up to

and compare it to -x.

this is the approach but I think the complexity is too high,I don't know

much about Functional segment tree, but feel it can also implement this

idea,but it is more and more complex..

if you know much better idea or find some error of this approach, please discuss it.