0_IQ_DOG's blog

Interesting Problem
By 0_IQ_DOG, history, 9 years ago, In English

You are given two arrays, A and B, with N (1<=N<=10^5) elements each. You need to support Q (1<=Q<=10^5) queries:

TYPE 1: QUERY i j — query the maximum element with index from i to j

TYPE 2: UPDATE i j — for every k between i and j (inclusive) set a[k]=b[k]+a[k]

EXAMPLE:

A: 1 2 3

B: 6 9 1

QUERIES:

QUERY 1 3 -> 3

UPDATE 1 3

QUERY 1 3 -> 11

EXPLANATION:

After the update operation, A becomes 1+6 2+9 3+1 = 7 11 4. Maximum of this array is clearly 11.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 0_IQ_DOG (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 0_IQ_DOG (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a link to this problem?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is just what I reduced 436F - Banners down to.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sqrt-Decomposition solves it.

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

    Can you explain how?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      ok,let's divide array into sqrt(n) blocks,each of them have a length sqrt(n). for each block we should count 2 value:

      1. how many times updated full subarray and for it sum of upd values(I mean block)
      2. what/where is the maximum value in the block

      then for each update (l,r,x) you should add x to each block 1st value,which are between l and r,there is 2 left and right remaining part,and for each you should update full block(new values,blocks 2nd new value which may not changed)

      for each query also you should see all blocks maximum values which are between (l,r) and also see remaining parts values.complexity is standart O(N + Q * sqrt(N))

      → Reply