(简单) HDU 3308 LCIS，线段树+区间合并。

　　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<iostream>

#include<cstdio>

#include<cstring>

#define lson L,M,po*2

#define rson M+1,R,po*2+1

#define lc po*2

#define rc po*2+1

using namespace std;

const int maxn=10e5+;

int mBIT[maxn*],lBIT[maxn*],rBIT[maxn*];

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]<num[M+])

    {

        mBIT[po]=max(mBIT[po],rBIT[lc]+lBIT[rc]);

        if(lBIT[lc]==len-(len/))

            lBIT[po]+=lBIT[rc];

        if(rBIT[rc]==(len/))

            rBIT[po]+=rBIT[lc];

    }

}

void build_tree(int L,int R,int po)

{

    if(L==R)

    {

        scanf("%d",&num[L]);

        mBIT[po]=lBIT[po]=rBIT[po]=;

        return;

    }

    int M=(L+R)/;

    build_tree(lson);

    build_tree(rson);

    pushUP(po,R-L+,M);

}

void update(int up,int L,int R,int po)

{

    if(L==R&&L==up)

        return;

    int M=(L+R)/;

    if(up<=M)

        update(up,lson);

    else

        update(up,rson);

    pushUP(po,R-L+,M);

}

int query(int ql,int qr,int L,int R,int po)

{

    if(ql<=L&&qr>=R)

        return mBIT[po];

    int M=(L+R)/;

    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+,min(qr,R),rson));

    int temp=min(rBIT[lc],M-ql+)+min(lBIT[rc],qr-M);

    if(num[M]<num[M+])                            //这里要判断！

        return max(ans,temp);

    else

        return ans;

}

int main()

{

    int N,M;

    int a,b;

    char c[];

    int T;

    cin>>T;

    while(T--)

    {

        scanf("%d %d",&N,&M);

        build_tree(,N-,);

        while(M--)

        {

            scanf("%s %d %d",c,&a,&b);

            if(c[]=='Q')

                printf("%d\n",query(a,b,,N-,));

            else

            {

                num[a]=b;

                update(a,,N-,);

            }

        }

    }

    return ;

}