Hi everyone!
I have just participated in an IT contest in my city recently. And there was a segment tree problem that for now, I cant think of the way to use the segment tree properly. Here's the problem:
Given an array a contains only two numbers: 1 and -1, all the elements index from 1 to n.
Input:
The first line contains two integer n and q (1 <= n,q <= 10^5), corresponding to the size of the array and number of operation. The next line contains array of integers of length n (a[i] ∈ {1;-1}). The next q following lines contain the description of the operations. The description of each operation is as follows:
- 1 i v: set the element with index i to v (1 <= i <= n, v ∈ {1;-1})
- 2 l r k (1 <= l <= r <= n, |k| <= n): this operation needs to find two number x, y (l <= x <= y <= r) such that the sum of all element from x to y equals to k.
Output
For each operation of the second type print the corresponding x, y. If no answer exists, print -1.
- Example:
I first approached this problem by doing some classic segment tree to find sum in a subsegment of the array, but I was soon realized that if I do that way, I can't find the proper way to find the number x and y. So I'm wonder what is the another way to approach this segment tree question more optimal.
And finally, thank you for reading my blog!
I can think of a way to answer each query in $$$O(\log^2 n)$$$.
First, create a segment tree that finds subarray sums and maintains the segments with minimum and maximum sums. To answer a query, find the minimum and maximum subsegment of $$$[l, r]$$$ in $$$O(\log n)$$$.
Denote the minimum sum as $$$MIN$$$, its segment as $$$[l_1,r_1]$$$, the maximum sum $$$MAX$$$, and its segment as $$$[l_2, r_2]$$$. Obviously, if $$$k \lt MIN$$$ or $$$k \gt MAX$$$, there is no answer. Otherwise, we claim that we can find an answer.
If $$$k \gt 0$$$, consider the segment $$$[l_2, r_2]$$$ (a maximal segment). It starts (and ends) with $$$1$$$, otherwise it would not be maximal. Then we can use binary search to find such an index $$$m$$$ ($$$m\in[l_2,r_2]$$$) that the sum on $$$[l_2, m]$$$ is exactly $$$k$$$. Binary search works because if, for example, the sum on $$$[l_2,x]$$$ is less than $$$k$$$, then the sum must grow as we move $$$x$$$ towards $$$r_2$$$.
If $$$k \lt 0$$$, we can use the minimum segment $$$[l_1,r_1]$$$ in the same manner.
Finally, if $$$k=0$$$, we do not use the segment tree; instead, we can maintain the indices of all ones and negative ones in sets and use set<int>::lower_bound to find the first $$$1$$$ and $$$-1$$$ with indices greater than or equal to $$$l$$$. One of these indices will be $$$l$$$, denote the other one $$$i$$$. The answer is $$$[i-1,i]$$$ unless $$$i$$$ does not exist or is greater than $$$r$$$.
I hope this helps!
can you tell the solution where the array does not consists of only 1 and -1s?
I doubt that a solution even exists. In any case, I cannot, sorry.
If k>0, consider the segment [l2,r2](a maximal segment). It starts (and ends) with 1, otherwise it would not be maximal ---> please help me here how can we say it starts with 1 only?
Because if it starts with a $$$-1$$$, we could exclude it from the segment and increase the sum on the segment. Therefore, the segment is not maximal.
The only exception here is when the whole segment $$$[l,r]$$$ consists only of $$$-1$$$, but then we would not be answering a query with $$$k \gt 0$$$.
Great idea! It was hard for me to realize why we can use binary search (the sum on the segment
[l2, m]is not monotonously increasing), but I did it."find the minimum and maximum subsegment of [l,r]" please clarify this. does subsegment here refer to the subarray sums min and max?
Yes, a minimum subsegment $$$[x,y]$$$ of $$$[l,r]$$$ here refers to a segment (i.e. subarray) that lies within $$$[l,r]$$$ ($$$l\le x\le y\le r$$$) and has the least sum across all subsegments of $$$[l,r]$$$. A maximum subsegment is one that has the greatest sum.
The proof of why binary search works here is pretty cool! It's also possible to reduce the complexity down to $$$O(log\,n)$$$ per query with fractional cascading.