You are not logged in. Please login at www.codechef.com to post your questions!

×

LRQUER - Editorial

1
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

EASY

PREREQUISITES:

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".

asked 26 Nov '17, 09:55

melfice's gravatar image

2★melfice
71825
accept rate: 0%

edited 27 Nov '17, 18:03

admin's gravatar image

0★admin ♦♦
19.0k348495533


Why my solution is giving wrong answer on subtask #2 but correct answer on subtasks #1 and #3. https://www.codechef.com/viewsolution/16377252

link

answered 27 Nov '17, 17:55

akash_321's gravatar image

4★akash_321
665
accept rate: 0%

Square root decomposition is also an easy and good option for this problem.

link

answered 30 Nov '17, 22:38

manishtanwar's gravatar image

5★manishtanwar
1
accept rate: 0%

https://www.codechef.com/viewsolution/16429490 only 2 subtasks of of task 1 working help followed the same approach as mentioned.

link

answered 03 Dec '17, 14:41

coldfire8549's gravatar image

3★coldfire8549
1
accept rate: 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 !!! :)

link

answered 12 Dec '17, 00:37

crypton's gravatar image

4★crypton
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,435
×3,199
×1,580
×96
×29

question asked: 26 Nov '17, 09:55

question was seen: 2,846 times

last updated: 12 Dec '17, 00:37