LR queries

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef has an array A of size N. His friend Chuwi playing with this array in a next way: he chooses a continuous subarray A[L..R] and finds the maximum of (A[M]  A[L]) * (A[R]  A[M]) over all values of M where L ≤ M ≤ R. Chef wants to hopple Chuwi and changes elements of his array sometimes. Please help Chuwi to solve this easy problem.Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two positive integers N denoting the number of elements in Chef's array and Q denoting the number of operations performed by Chef and Chuwi. The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the Chef's array. Next Q contains three integers  type = 1 L R denoting that Chuwi takes subarray A[L..R] and finds the maximum of his function. type = 2 X Y denoting that Chef changes element A[X] by Y.
Output
For every Chuwi's performed operation output the maximal value in a single line.
Constraints
 1 ≤ T ≤ 1000
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i}, Y ≤ 10^{9}
 1 ≤ L ≤ R ≤ N
 1 ≤ X ≤ N
 1 ≤ type ≤ 2
 Sum of N over all test cases ≤ 2*10^{5}
 Sum of Q over all test cases ≤ 2*10^{5}
Subtasks
 Subtask #1: (20 points) sum of N over all test cases ≤ 5*10^{3} and sum of Q over all test cases ≤ 5*10^{3} and TL = 1 sec
 Subtask #2: (30 points) 1 ≤ A_{i}, Y ≤ 10^{2}
 Subtask #3: (50 points) Original constraints
Example
Input: 1 4 3 2 1 4 3 1 1 4 2 2 3 1 1 3 Output: 0 1
Explanation
Example case 1. For Chuwi's subarray [2, 1, 4, 3] there are 4 possible values of (A[M]  A[L]) * (A[R]  A[M])  {0, 2, 2, 0} correspondingly, maximal value will be 0. After the second operation array will be [2, 3, 4, 3]. And for Chuwi's subarray [2, 3, 4] possible 3 values  {0, 1, 0}, hence answer is 1.
Author:  mgch 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/LRQUER 
Tags  easy, ltime54, mgch, segmenttree 
Date Added:  20112017 
Time Limit:  1  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 