LRQUER - Editorial

melfice · November 26, 2017, 9:55am

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.

You’re given L and R. Find such M that (A_R-A_M)(A_M-A_L) is maximized.
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.