The Problem Set

All submissions for this problem are available.
As we all know that team LaZyProblemSetters is gearing up for ICPC 2015 and have finally reached in front of a computer together to solve a problem set. Since they have already wasted too much time procrastinating, they have decided to manage the problem set with more caution. They are now ordering the problems according to their difficulty levels instead of solving all the easy problems as they used to do earlier.
For this practice round, everybody has pitched in a few problems of their choice. So in the end, they have a set of N problems ordered as P_{1}, ..., P_{N}, where P_{i} denotes the i^{th} problem. For each problem that was brought in by any team member, he assigned an integer D_{i} which according to him is the difficulty level of that problem.
The difficulty level assigned to a problem is exactly the number of time units one expects to solve that particular problem. However, as we all know, that assigning difficulty to a problem is really subjective and the assigned difficulty level of the problem may change when all the three team members look at that problem. Since, they are busy solving the problem, they have asked you to help in giving them the information they need about the problem set.
Following is the list of all of their requirements, for which they need your help:
 Update the difficulty level of a problem.
 Tell them the difficulty level of the most difficult problem in the problem set.
 The total time it would take them to solve a set of problems.
 Whether a list of consecutive problems are in some order of difficulty.
 P_{x} to P_{y} are in increasing order of difficulty if D_{x}≤ D_{x+1}≤ ... ≤ D_{y}
 P_{x} to P_{y} are in decreasing order of difficulty if D_{x}≥ D_{x+1}≥ ... ≥ D_{y}
To make it easier, faster and accurate, they have decided to communicate with you as follows:
 U x d
The difficulty level of the problem P_{x} has been updated to d. Hence D_{x} = d.  M x y
What is the difficulty level of the most difficult problem in range P_{x}, ..., P_{y}.  S x y
How much total time it would take them to solve all the problems in range P_{x}, ..., P_{y}.  I x y
Whether the problems in range P_{x}, ..., P_{y} are in increasing order of difficulty. Print 1 if they are, 0 otherwise.  D x y
Whether the problems in range P_{x}, ..., P_{y} are in decreasing order of difficulty. Print 1 if they are, 0 otherwise.
Input
First line will have two space separated integers N and M denoting the number of problems and the number of operations that you are asked to perform for the LaZyProblemSetters.
Next line will have N space separated integers where the i^{th} integer denotes D_{i}.
Next M lines will each represent one of the five operations mentioned above in the form U x d or O x y where O is from the set {M,S,I,D}.
Output
Print one line with the answer corresponding to each operation of the form O x y where O is from the set {M,S,I,D}.
Constraints
 1 ≤ x ≤ y ≤ N ≤ 10^{5}
 1 ≤ M ≤ 5*10^{5}
 1 ≤ D_{i}, d ≤ 10^{9}
 O is a character from {M,S,I,D}
Example
Input: 5 7 1 2 4 5 10 S 1 5 S 1 4 M 1 5 I 2 4 U 2 11 M 1 5 D 3 4 Output: 22 12 10 1 11 0
Note: Large I/O, be careful with certain languages
Author:  admin 
Editorial  http://discuss.codechef.com/problems/ACM14KN4 
Tags  acmkan14, admin, easymedium, segmenttree 
Date Added:  4102014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
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. 