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.
Auto comment: topic has been updated by 0_IQ_DOG (previous revision, new revision, compare).
Auto comment: topic has been updated by 0_IQ_DOG (previous revision, new revision, compare).
Is there a link to this problem?
This is just what I reduced 436F - Banners down to.
Sqrt-Decomposition solves it.
Can you explain how?
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:
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))
Numbers in array B are not constant though.. so how will you update maximum?
maximum=a[maxi]+b[maxi]*upd[block]