Oanh_va_Khoi's blog

I need solution of this problem
By Oanh_va_Khoi, history, 3 days 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

»
3 days ago, # |
  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
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Iwo items have to be in the lower half and one in the upper. I guess this would be the idea if its not Im sorry i wasnt able to help

      → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Two queries for the halves amd when the range length is odd you would take the lover half to be even

      → Reply
»
3 days ago, # |
  Vote: I like it +4 Vote: I do not like it

It's obvious that if there exists $$$x < i < 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) > \max_{x<i<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
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thank you a lot :D :D :D

    I did not think about posible (x, y) just satisfies min(ax, ay) > max(ai)

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply