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.
↵
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.
