HDU 3308 线段树求区间最长连续上升子序列长度

题意：两种操作，Q L R查询L - R 的最长连续上升子序列长度，U pos val 单点修改值

#include <bits/stdc++.h>

#define N 100005

using namespace std;

int lcs[N<<],pre[N<<],suf[N<<],arr[N];维护区间lcs长度，以左端点为起点的lcs长度，以右端点为终点的lcs长度，这么做是为了处理区间合并后区间总lcs值的更新

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

{

    int m=(l+r)>>;

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

    if(arr[m]<arr[m+])lcs[rt]=max(lcs[rt],suf[rt<<]+pre[rt<<|]);

    pre[rt]=pre[rt<<];

    if(pre[rt<<]==m-l+&&arr[m]<arr[m+])pre[rt]+=pre[rt<<|];

    suf[rt]=suf[rt<<|];

    if(suf[rt<<|]==r-m&&arr[m]<arr[m+])suf[rt]+=suf[rt<<];

}

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

{

    if(l==r)

    {

        suf[rt]=pre[rt]=lcs[rt]=;

        return;

    }

    int m=(l+r)>>;

    build(l,m,rt<<);

    build(m+,r,rt<<|);

    pushup(l,r,rt);

}

void update(int pos,int val,int l,int r,int rt)

{

    if(l==r)

    {

        arr[l]=val;

        return;

    }

    int m=(l+r)>>;

    if(pos<=m)update(pos,val,l,m,rt<<);

    if(pos>m)update(pos,val,m+,r,rt<<|);

    pushup(l,r,rt);

}

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

{

    if(L<=l&&r<=R)return lcs[rt];

    int m=(l+r)>>;

    int mx=;

    if(L<=m)mx=max(mx,query(L,R,l,m,rt<<));

    if(m<R)mx=max(mx,query(L,R,m+,r,rt<<|));//这时的mx只是各子区间的最大值，必须考虑子区间连接之后的状态

    int prex=min(R-m,pre[rt<<|]);

    int sufx=min(m-L+,suf[rt<<]);

    if(arr[m]<arr[m+])mx=max(mx,prex+sufx);

    return mx;

}

int main()

{

    int t,n,m;

    cin>>t;

    while(t--)

    {

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

        for(int i=;i<=n;i++)scanf("%d",arr+i);

        build(,n,);

        char cmd[];

        int l,r;

        while (m--)

        {

            scanf("%s%d%d",cmd,&l,&r);

            if(cmd[]=='U')update(l+,r,,n,);

            else printf("%d\n",query(l+,r+,,n,));

        }

    }

    return ;

}