I need solution of this problem

Блог пользователя DCSNMGPSSIK

Автор DCSNMGPSSIK, история, 19 месяцев назад, По-английски

Hello Codeforces — ers,

I have this problem need to solve

Given an array a with N integers (1 <= N <= 500000)

Given Q queries (1 <= Q <= 100000), for each query, we have 2 integers L and R, we have to find the maximum value of a[x] + a[y] + a[z] with sastifies:

. L <= x < y < z <= R . y — x < z — y

Thanks a lot :D

DCSNMGPSSIK
19 месяцев назад
7

Комментарии (5)

Показать архивные | Написать комментарий?

jakeob

19 месяцев назад, скрыть # |

Persistent segment tree probably. You can find the idea at cp-algo advanced segment tree section.

→ Ответить

DCSNMGPSSIK

19 месяцев назад, скрыть # ^ |

of course I know Persistent Segment tree, but how to solve it :D :D :D. The main idea ?

→ Ответить

Portulaca

19 месяцев назад, скрыть # |

It's obvious that if there exists $$$x \lt i \lt y$$$ such that $$$a_i \ge \min(a_x,a_y)$$$, we can replace $$$x$$$ with $$$i$$$(or replace $$$y$$$ with $$$i$$$).

So all the possible $$$(x,y)$$$ satisfies the condition that $$$\min(a_x,a_y) \gt \max_{x \lt i \lt y} a_i$$$.

It can be proved that there exists only $$$O(n)$$$ pairs of legal $$$(x,y)$$$.

And the rest of the problem can be solved with segment tree offline(persistent segment tree is not needed).

You can refer to https://www.luogu.com.cn/problem/P11392.

→ Ответить