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].

 

　　题目大意就是给你一个数列，求区间内的最长连续子序列。以及对某一个点的值进行更改。

　　线段树维护区间内的LCIS，前缀LCIS，后缀LCIS就可。

 

代码如下：

#include
      
       #include
       
        #include
        
         #define lson L,M,po*2#define rson M+1,R,po*2+1#define lc po*2#define rc po*2+1using namespace std;const int maxn=10e5+10;int mBIT[maxn*4],lBIT[maxn*4],rBIT[maxn*4];int num[maxn];void pushUP(int po,int len,int M){    mBIT[po]=max(mBIT[lc],mBIT[rc]);    lBIT[po]=lBIT[lc];    rBIT[po]=rBIT[rc];    if(num[M]
         
          =R)        return mBIT[po];    int M=(L+R)/2;    if(qr<=M)        return query(ql,qr,lson);    if(ql>M)        return query(ql,qr,rson);    int ans=max(query(max(ql,L),M,lson),query(M+1,min(qr,R),rson));    int temp=min(rBIT[lc],M-ql+1)+min(lBIT[rc],qr-M);    if(num[M]
          
           >T;    while(T--)    {        scanf("%d %d",&N,&M);        build_tree(0,N-1,1);        while(M--)        {            scanf("%s %d %d",c,&a,&b);            if(c[0]=='Q')                printf("%d\n",query(a,b,0,N-1,1));            else            {                num[a]=b;                update(a,0,N-1,1);            }        }    }    return 0;}