【HDU3308】LCIS

题目大意：维护一个长度为 N 的序列，支持单点修改，区间查询最长连续上升子序列的长度。

题解：
线段树维护一段区间左端点开始的 LCIS 长度，右端点开始的 LCIS 长度以及区间最优解。考虑进行合并，合并后区间的最优解可能由三部分构成，即：左区间的最优解、右区间的最优解和左区间rmx+右区间lmx的值。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

int n,m,a[maxn];
struct node{
    #define ls(o) t[o].lc
    #define rs(o) t[o].rc
    int lc,rc,lmx,rmx,mx;
}t[maxn<<1];
int tot,root;
inline void pushup(int o,int l,int r){
    int mid=l+r>>1;
    t[o].mx=max(max(t[ls(o)].mx,t[rs(o)].mx),a[mid]<a[mid+1]?t[ls(o)].rmx+t[rs(o)].lmx:0);
    t[o].lmx=t[ls(o)].lmx==mid-l+1&&a[mid]<a[mid+1]?t[ls(o)].lmx+t[rs(o)].lmx:t[ls(o)].lmx;
    t[o].rmx=t[rs(o)].rmx==r-mid&&a[mid]<a[mid+1]?t[rs(o)].rmx+t[ls(o)].rmx:t[rs(o)].rmx;
}
int build(int l,int r){
    int o=++tot;
    if(l==r){t[o].lmx=t[o].rmx=t[o].mx=1;return o;}
    int mid=l+r>>1;
    ls(o)=build(l,mid),rs(o)=build(mid+1,r);
    pushup(o,l,r);
    return o;
}
void modify(int o,int l,int r,int pos){
    if(l==r)return;
    int mid=l+r>>1;
    if(pos<=mid)modify(ls(o),l,mid,pos);
    else modify(rs(o),mid+1,r,pos);
    pushup(o,l,r);
}
int query(int o,int l,int r,int x,int y){
    if(l==x&&r==y)return t[o].mx;
    int mid=l+r>>1;
    if(y<=mid)return query(ls(o),l,mid,x,y);
    else if(x>mid)return query(rs(o),mid+1,r,x,y);
    else{
        int ansl=query(ls(o),l,mid,x,mid);
        int ansr=query(rs(o),mid+1,r,mid+1,y);
        int ret=0;
        if(a[mid]<a[mid+1])ret=min(t[ls(o)].rmx,mid-x+1)+min(t[rs(o)].lmx,y-mid);
        return max(ret,max(ansl,ansr));
    }
}

void read_and_parse(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    root=build(1,n);
}
void solve(){
    char opt[2];
    int x,y;
    while(m--){
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='Q')++x,++y,printf("%d\n",query(root,1,n,x,y));
        else ++x,a[x]=y,modify(root,1,n,x);
    }
}
void init(){memset(t,0,sizeof(t)),tot=0;}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        init();
        read_and_parse();
        solve();
    }
    return 0;
}

【HDU3308】LCIS

原文：https://www.cnblogs.com/wzj-xhjbk/p/10951171.html