Hi everyone. Today I encountered a data structures problem, which is a slight swist on standart segment tree problem.

You are given an array *A* of size *N*. *N ≤ 10^5, A[i] ≤ 10^6,* You need to process 3 types of queries

Print the sum of all integers ai where

*L ≤ i ≤ R.*Add x to each integer ai where

*L ≤ i ≤ R.*For each integer

*A[i]*where*L ≤ i ≤ R*, replace it with*floor(sqrt(A[i]))*. Where*sqrt(a)*is the square root of*a*, and*floor(b)*is the integer value of*b*after removing everything on the right of the decimal point.

There can be *Q≤20000* queries.

If we didn't have type 3 query, then we are left with standard lazy segment tree problem.

How to handle 3rd type queries?

I think the problem you are talking about was in ACPC 2016, this problem to be exact.

I didn't solve it, however, I was told by one of the judges during the contest that it can be solved by holding the maximum and minimum in the range of the segment tree and using lazy propagation in the form of vectors and since any range will become equal after not that much operations when the maximum becomes equal to minimum it's easy to note that lazy propagation becomes easier to do in O(1).

I don't know exact time complexity of this solution. Firstly we store maximum and minimum in our segment tree. We will have three options.

Can you please explain the 2nd option?

How can we obtain it(the new version of the segment, after applying

sqrt) by addingto this segment elements?(sqrt(minimum) — minimum)It can be done using segment tree with lazy propagation which supports adding and assigning. We can support it just only using one segment tree.

I mean the following:

Suppose the segment is

[11,5,7,10,6]After applying

sqrtwe should get[3,2,2,3,2]right?But if we do it your way i.e. by adding (sqrt(minimum) — minimum) to this segment — we get

sqrt(minimum) — minimum = sqrt(5) — 5 = -3So we add

-3to the range and get[8,2,4,7,3]. Which is different than[3,2,2,3,2].We will have an array [11, 5, 7, 10, 6]. No condition meets. (11 — 5 != 1)

So, we will divide it into two [11, 5], [7, 10, 6]. Also no condition meets.

[11], [5], [7], [10, 6]

[11], [5], [7], [10], [6] => [3,2,2,3,2]

Thanks Zharaskhan got your point. Can you provide intuition why this works fast? In this query example we saw that it is linear.

I think the idea is if

max-min≥ 2, then it will decrease proportional tosqrt(N). So 2nd type queries won't ruin everything because the difference will still decrease quickly.But it's possible that

max-min= 1 and still will be after taking square roots for each element. For example [3, 4] to [1, 2]. So if we're able to do such updates without solving recursively, we can solve the problem.If we know

min=max- 1 then we can, for example, use counts for min or max and update the interval without the need of recursive.That's nice solution.

What is the complexity of this solution?

Thank you!

Would the solution be considerably worse if we solve option 2 recursively?

EDIT: Nevermind, I finally understood the corner case.

For query type 3:

when we get the range modification entry, we can modify each element in the range one by one, and hence perform (R — L + 1) single element update queries. This approach would be to slow, as it makes the complexity of range update query to O ((R — L + 1) lg N). But many of these single element update queries can be ignored, and the number of actual performed queries is much lower.

Note that, if the value of an element A[x] is 1, then update query on A[x] does not have any effect on the segment tree.Let call such queries as degenerate queries, and We can discard them. Now think A[x]>1, then how many update operation is required on that position to make the A[x] is 1. It will require less than lg(A[x]) operation approximately.So,every node of segment tree gets updated at most lg(10^6) time . However, now the problem is how to find the non-degenerate single element update queries for the range [L, R]. For this purpose, we maintain another information in the segment tree node, which is the number of elements in the range which are larger than one.

Similar problem You can see editorial for better explanation .

What if we have lots of 2nd type queries, such that

A[i]is never becoming 1? This way the complexity may be uptoO(n)for each query.My guess is that you can do it with a small modification to the lazy segment tree. For each node in the tree keep track of whether or not its corresponding interval is constant. Then when you get a query of type 3, you can lazily take care of it if the interval is constant, otherwise let the children nodes handle the query.

The reason why I think that this works is that floor(sqrt( )) is really destructive. Suppose you start out with

A[i] ≥ 1, then after you apply query 3 enough times to it, the new value is independent of its original value. You would have gotten the exact same result hadA[i] = 1 in the beginning. This in turn makes intervals become constant, which allows queries of type 3 to be taken care of lazily.It seems like a good idea. Btw do you have an intuitive reasoning why should the invervals become constant quickly? We have 2nd type queries which may ruin everything.

Also do you have an estimate of time complexity? In the worst case it may be linear per query, this can happen if all internal(non-leaf) segments aren't constant.

(Note there is a small error in my approach, so just use Zharaskhan approach, still here is the analysis for the running time)

Assuming that

x>y≥ 1, from .one can show that

.

This describes how quickly the difference between two values

x,ydecreases when you apply a floor(sqrt( )) on the pair. It will pretty much decrease with a factor of , so it decreases very quickly.I did some calculations given the second inequality and from that I concluded that it takes at most 5 iterations for the difference to become ≤ 1.

Finally, about the running time. For each node in the tree you need to apply type3 queries 5 times to reach

max-min≤ 1. Also whenever you do a type2 or type3 query you will update nodes, which after 5 type3 updates will go back to havemax-min≤ 1. So from this I conclude that the running time should be something like .If you have 3s and 4s and alternate sqrts and +=2 I think you'll never get constant and you will have linear sqrt updates

Thanks for pointing that out, that is a problem.

I think it is possible to fix it by keeping track of whether or not the interval only contains at most two different values (and keep a count for both). But if you do that, then you might as well just do the min/max approach that Zharaskhan mentioned.

Can I submit this problem somewhere? It seems the ICPC Live Archive doesn't have any input (my assertion

`assert(ntest > 0)`

failed).I can't think of an Segment Tree solution so here goes my shitty sqrt one:

SpoilerLet's process one block of

Tqueries at a time (we will chooseTlater). We divide theNnumbers into intervals, with starting points beingL[1],L[2], ...,L[T],R[1] + 1,R[2] + 1, ...,R[T] + 1. This way we have at most 2Tintervals, and each query cover some intervals completely. For each interval, we store those values: min, max, sum, offset, count of elements equal to min/max.For the "add X" queries, we simply increase the offset of the affected intervals by

X.For the "take sqrt" queries, we notice that after

at most6 "sqrt" queries,max[b] -min[b] ≤ 1 will hold, because the value ofA[i] won't exceed 2^{26}and the "add" queries won't changemax[b] -min[b]. Thus, ifmax[b] -min[b] > 1 holds at the moment, we just recompute all elements of blockb, knowing we won't do that more than 6 times per block, and update the min, max, and sum accordingly. Otherwise, we can set`min[b] = sqrt(min[b] + offset[b]), max[b] = sqrt(max[b] + offset[b]);`

and ignore value`sum`

because it can be deduced (see below).For the "compute sum" queries, we compute the sum of each block. For block

b:If

min[b] =max[b] thensum[b] =min[b] *cnt_{min}[b] +offset[b] *length[b].If

min[b] + 1 =max[b] thensum[b] =min[b] *cnt_{min}[b] +max[b] *cnt_{max}[b] +offset[b] *length[b].Otherwise, we just return

sum[b].After processing T queries, we need to retrieve the new array

A(I did that inO(N*log(N)), not sure if it can be done faster).The time complexity is , where 6 =

log_{2}(log_{2}(maxA)).Code with T = 500 that produces the same answer as my brute force solution

Probably you can download here: http://acmacpc.org/archive/y2017/

I tried but it says "404 page not found"...

I think you can submit the problem from here :

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=804&page=show_problem&problem=6491

Already did but my assertion

`assert(ntest > 0);`

fails, which likely means the judge has no input.