Home STD Contest Notification Clarification Problems Ranklist Status Print Sign Out
SolutionMore...

LCIS

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 174    Accepted Submission(s): 19


Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
 

Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
 

Output
For each Q, output the answer.
 

Sample Input
1 10 10 7 7 3 3 5 9 9 8 1 8 Q 6 6 U 3 4 Q 0 1 Q 0 5 Q 4 7 Q 3 5 Q 0 2 Q 4 6 U 6 10 Q 0 9
 

Sample Output
1 1 4 2 3 1 2 5
 

Author
notonlysuccess
 

Statistic | Submit | Clarifications | Back