Interesting Problem

Правка en2, от 0_IQ_DOG, 2015-06-13 04:25:38

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский 0_IQ_DOG 2015-06-13 04:25:59 6
en2 Английский 0_IQ_DOG 2015-06-13 04:25:38 2 Tiny change: 'm i to j\nTYPE 2: ' -> 'm i to j\n\nTYPE 2: '
en1 Английский 0_IQ_DOG 2015-06-13 04:25:19 512 Initial revision (published)