LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3717 Accepted Submission(s): 1660
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].
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).
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
shǎ崽
Source
HDOJ Monthly Contest – 2010.02.06
传送门:HDU 3308 LCIS
题目大意:有两种操作,1、修改单点的值,2、询问一段区间内的连续上升序列LCIS。
题目分析:就是维护左端点,右端点,左右连续最大LCIS以及区间内最大LCIS,其他没了。
传送门:HDU 3308 LCIS
题目大意:有两种操作,1、修改单点的值,2、询问一段区间内的连续上升序列LCIS。
题目分析:就是维护左端点,右端点,左右连续最大LCIS以及区间内最大LCIS,其他没了。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define ll o << 1 #define rr o << 1 | 1 #define lson l , m , ll #define rson m + 1 , r , rr const int maxN = 1000000 ; int lnum[maxN] , rnum[maxN] ; int lmax[maxN] , rmax[maxN] , mmax[maxN] ; int max ( const int X , const int Y ) { if ( X > Y ) return X ; return Y ; } int min ( const int X , const int Y ) { if ( X < Y ) return X ; return Y ; } void PushUp ( int o , int len ) { lnum[o] = lnum[ll] ; rnum[o] = rnum[rr] ; lmax[o] = lmax[ll] ; rmax[o] = rmax[rr] ; mmax[o] = max ( mmax[ll] , mmax[rr] ) ; if ( rnum[ll] < lnum[rr] ) { mmax[o] = max ( mmax[o] , rmax[ll] + lmax[rr] ) ; if ( lmax[ll] == len - ( len >> 1 ) ) { lmax[o] += lmax[rr] ; } if ( rmax[rr] == ( len >> 1 ) ) { rmax[o] += rmax[ll] ; } } } void Build ( int l , int r , int o ) { if ( l == r ) { int x ; scanf ( "%d" , &x ) ; lnum[o] = rnum[o] = x ; lmax[o] = mmax[o] = rmax[o] = 1 ; return ; } int m = ( l + r ) >> 1 ; Build ( lson ) ; Build ( rson ) ; PushUp ( o , r - l + 1 ) ; } void Update ( int x , int v , int l , int r , int o ) { if ( l == r ) { lnum[o] = rnum[o] = v ; lmax[o] = mmax[o] = rmax[o] = 1 ; return ; } int m = ( l + r ) >> 1 ; if ( x <= m ) Update ( x , v , lson ) ; else Update ( x , v , rson ) ; PushUp ( o , r - l + 1 ) ; } int Query ( int L , int R , int l , int r , int o ) { if ( L <= l && r <= R ) return mmax[o] ; int m = ( l + r ) >> 1 ; int tmp1 = 0 , tmp2 = 0 , tmp3 = 0 ; if ( L <= m ) tmp1 = Query ( L , R , lson ) ; if ( m < R ) tmp2 = Query ( L , R , rson ) ; if ( L <= m && m < R && rnum[ll] < lnum[rr] ) tmp3 = min ( m - L + 1 , rmax[ll] ) + min ( lmax[rr] , R - m ) ; return max ( max ( tmp1 , tmp2 ) , tmp3 ) ; } void work () { int n , m , First , Second ; char ch[5] ; scanf ( "%d%d" , &n , &m ) ; Build ( 1 , n , 1 ) ; while ( m -- ) { scanf ( "%s%d%d" , ch , &First , &Second ) ; if ( ch[0] == 'U' ) Update ( First + 1 , Second , 1 , n , 1 ) ; else printf ( "%d\n" , Query ( First + 1 , Second + 1 , 1 , n , 1 ) ) ; } } int main () { int T ; scanf ( "%d" , &T ) ; while ( T -- ) { work () ; } return 0 ; }