hdu3308

区间合并比较模板的题，就是求一个区间的LCIS

线段树维护左最大LCIS，右最大LCIS，区间LCIS

看代码就行

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define maxn 100005

int lval[maxn<<],rval[maxn<<];//Çø¼ä×óÓҶ˵ãÖµ

int lmx[maxn<<],rmx[maxn<<],mx[maxn<<];//Çø¼ä×ó²àLCIS£¬Çø¼äÓÒ²àLCIS£¬Çø¼äLCIS

inline void pushup(int rt,int l,int r){

    lval[rt]=lval[rt<<];rval[rt]=rval[rt<<|];//¸üÐÂ×óÓҶ˵ã

    //¸üÐÂ×óÓÒLCISºÍLCIS

    lmx[rt]=lmx[rt<<];//×ó¶Ë

    rmx[rt]=rmx[rt<<|];//ÓÒ¶Ë

    mx[rt]=max(mx[rt<<],mx[rt<<|]);

    int m=l+r>>;

    int lenl=m-l+,lenr=r-m;//×óÓÒ×ÓÇø¼ä³¤¶È

    if(rval[rt<<]<lval[rt<<|]){//ºÏ²¢

        if(lmx[rt<<]==lenl)

            lmx[rt]+=lmx[rt<<|];

        if(rmx[rt<<|]==lenr)

            rmx[rt]+=rmx[rt<<];

        mx[rt]=max(mx[rt],rmx[rt<<]+lmx[rt<<|]);

    }

    mx[rt]=max(mx[rt],max(lmx[rt],rmx[rt]));

}

void build(int l,int r,int rt){

    if(l==r){

        scanf("%d",&lval[rt]);

        rval[rt]=lval[rt];

        lmx[rt]=rmx[rt]=mx[rt]=;

        return;

    }

    int  m=l+r>>;

    build(lson);

    build(rson);

    pushup(rt,l,r);

}

void update(int pos,int c,int l,int r,int rt){

    if(l==r){

        lval[rt]=rval[rt]=c;

        return;

    }

    int m=l+r>>;

    if(pos<=m) update(pos,c,lson);

    else if(pos>m) update(pos,c,rson);

    pushup(rt,l,r);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l && R>=r){

        return mx[rt];

    }

    int m=l+r>>;

    if(R<=m) return query(L,R,lson);//Èç¹û[L,R]ÔÚ×óÇø¼ä

    else if(L>m) return query(L,R,rson);

    else {//µ½Á½¸öÇø¼äÀï²éÕÒ

        int temp1=query(L,R,lson);

        int temp2=query(L,R,rson);

        int temp3=;

        if(rval[rt<<]<lval[rt<<|]){

            temp3+=min(m-L+,rmx[rt<<]);

            temp3+=min(R-m,lmx[rt<<|]);

        }

        /*return max(temp3,max(temp1,temp2));*///¶ÔÓÚÁ½¸ö×ÓÇø¼ä£¬Ö»ÓÐÈýÖÖÇé¿ö×÷Ϊ×îÖÕ½á¹û£¬Ò»ÊÇ×óÇø¼äµÄLCIS£¬¶þÊÇÓÒÇø¼äµÄLCIS£¬ÈýÊǺϲ¢ºóÖмäµÄÄÇÒ»¶Î

        return max(max(temp1,temp2),temp3);

    }

}

int main(){

    int T,n,q;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&q);

        build(,n-,);

        int a,b;

        char op[];

        while(q--){

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

            if(op[]=='Q') printf("%d\n",query(a,b,,n-,));

            else update(a,b,,n-,);

        }

    }

    return ;

}