DCSNMGPSSIK's blog

I need solution of this problem
By DCSNMGPSSIK, history, 15 months ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://oj.uz/problem/view/JOI19_jumps

→ Reply