LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2640 Accepted Submission(s): 1143 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<=10 5). The next line has n integers(0<=val<=10 5). The next m lines each has an operation: U A B(0<=A,n , 0<=B=10 5) 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
1 /** 2 这是一道经典的线段树题目。 3 有分治的思想在里面 4 求解区间[L , R]最长递增子序列的长度。 5 6 对于一个线段树的区间 7 我们需要保存左端点的值,右端点的值, 8 以及分别包含左右端点所能达到的最长递增子序列的长度 9 lmaxn ,rmaxn;还要有一个保存区间最彻底子序列的值maxn。 10 11 **/ 12 #include13 #include 14 #include 15 #include 16 using namespace std; 17 18 struct node 19 { 20 int l,r,len; 21 int lnum,rnum,lmaxn,rmaxn,maxn; 22 }f[100002*4]; 23 int date; 24 25 /** 26 向上更新函数。 27 **/ 28 void up(int n,int LChild,int RChild) 29 { 30 f[n].lnum = f[LChild].lnum; 31 f[n].rnum = f[RChild].rnum; 32 33 f[n].lmaxn = (f[LChild].lmaxn==f[LChild].len && f[LChild].rnum =wz) update(wz,num,n*2); 76 else if(mid =r) return query(l,r,n*2); 88 else if(mid