×

# LRQUER - Editorial

Author: Misha Chorniy
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

EASY

Segment tree

# PROBLEM:

You're given array $A$ of $N$ elements. You have to answer queries of two types.

1. You're given $L$ and $R$. Find such $M$ that $(A_R-A_M)(A_M-A_L)$ is maximized.
2. Change $A_X$ to $Y$.

# QUICK EXPLANATION:

The problem is equivalent to the finding element closest to $\dfrac{A_L+A_R}{2}$ on the segment $[L;R]$ and processing update queries.

# EXPLANATION:

You have to find $A_M$ which minimizes $A_M^2-(A_L+A_R)A_M+A_RA_L$. For this function we want to have $A_M$ as close as possible to the extremum of parabola which is $Z=\dfrac{A_L+A_R}{2}$. So you can reduce this to the queries of lower bound on the segment which is well-known segment tree excercise.

To solve it you have to keep multiset of all values that occur on the segment in each vertex of segment tree, this will allow you to update in $O(\log^2 N)$ by erasing old value and inserting new one in each multiset of vertices which cover position $X$. Also you can get queries in $O(\log^2 N)$ by simply asking lower-bound in each multiset of vertices you decomposed query segment in. You should also compress values, i.e. sort them and assign to each number its order in sorted sequence. This will allow to simplify algorithm and lower time and memory consumes. However one probably can solve the problem with dynamic segment tree instead of compression. Considering the compression to be done, this will look as follows:

multiset<int> st[4 * maxn];

// Inserts or erases element depending on its sign
void update(int p, int c, int v = 1, int l = 0, int r = maxn) {
if(c < 0) {
st[v].erase(st[v].lower_bound(-c));
} else {
st[v].insert(c);
}
if(r - l == 1) {
return;
}
int m = (l + r) / 2;
if(pos < m) {
update(p, c, 2 * v, l, m);
} else {
update(p, c, 2 * v + 1, m, r);
}
}

// Returns closest element to c from intersection of [a, b) and [l, r)
int nearest(int a, int b, int c, int v = 1, int l = 0, int r = maxn) {
if(a <= l && r <= b) {
auto it = st[v].lower_bound(c);
int res = inf;
for(int i = 0; i <= 1; i++) {
if(it != end(st[v])) {
res = abs(res - c) < abs(*it - c) ? res : *it;
}
if(it != begin(st[v])) {
it--;
}
}
return res;
} else if(r <= a || b <= l) {
return inf;
}
int m = (l + r) / 2;
int A = nearest(a, b, c, 2 * v, l, m);
int B = nearest(a, b, c, 2 * v + 1, m, r);
return abs(A - c) < abs(B - c) ? A : B;
}


# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

# RELATED PROBLEMS:

This question is marked "community wiki".

4★melfice
811837
accept rate: 0%

19.8k350498541

 0 Why my solution is giving wrong answer on subtask #2 but correct answer on subtasks #1 and #3. https://www.codechef.com/viewsolution/16377252 answered 27 Nov '17, 17:55 76●5 accept rate: 0%
 0 Square root decomposition is also an easy and good option for this problem. answered 30 Nov '17, 22:38 1●1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/16429490 only 2 subtasks of of task 1 working help followed the same approach as mentioned. answered 03 Dec '17, 14:41 0●2 accept rate: 0%
 0 @coldfire8549 I think you haven't cleared the tree vector before starting a new test case.Use vector.clear(). It will work. Happy Coding !!! :) answered 12 Dec '17, 00:37 4★crypton 1 accept rate: 0%
 0 Can somebody share the square root decomposition method for this problem here? TIA answered 04 Sep '18, 11:05 1●1 accept rate: 0%
 0 my solution using square root decomposition answered 06 Feb, 20:44 120●5 accept rate: 20%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,678
×3,763
×1,755
×98
×29

question asked: 26 Nov '17, 09:55

question was seen: 3,262 times

last updated: 06 Feb, 20:44