(中等) UESTC 360 Another LCIS ，线段树+区间更新。

Description：

　　For a sequence S1,S2,⋯,SN, and a pair of integers (i,j), if 1≤i≤j≤N and Si<Si+1<Si+2<⋯<Sj−1<Sj, then the sequence Si,Si+1,⋯,Sj is a CIS(Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).

In this problem, we will give you a sequence first, and then some add operations and some query operations. An add operation adds a value to each member in a specified interval. For a query operation, you should output the length of the LCIS of a specified interval.

　　题目大意就是说求一段区间的最大上升子序列（注意这里的子序列必须是连续的。）

　　对线段树维护前缀最大上升子序列，后缀最大上升子序列，最大上升子序列，以及区间左端点的值，右端点的值。

　　这里要注意如果pushUP时，左子树前缀为其长度，那么父亲的前缀的长度应该为左的加右的，右子树同理。

代码如下：

#include<iostream>

#include<cstdio>

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define lson L,M,po*2

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

using namespace std;

struct state

{

    int lef,rig,mid;

    int x,y;

};

int N,Q;

state BIT[*];

int COL[*];

int num[];

void pushDown(int po)

{

    if(COL[po])

    {

        COL[po*]+=COL[po];

        COL[po*+]+=COL[po];

        BIT[po*].x+=COL[po];

        BIT[po*].y+=COL[po];

        BIT[po*+].x+=COL[po];

        BIT[po*+].y+=COL[po];

        COL[po]=;

    }

}

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

{

    BIT[po].mid=max(BIT[po*].mid,BIT[po*+].mid);

    BIT[po].lef=BIT[po*].lef;

    BIT[po].rig=BIT[po*+].rig;

    BIT[po].x=BIT[po*].x;

    BIT[po].y=BIT[po*+].y;

    int M=(L+R)/;

    if(BIT[po*].y<BIT[po*+].x)

    {

        BIT[po].mid=max(BIT[po].mid,BIT[po*].rig+BIT[po*+].lef);

        if(BIT[po*].lef==M-L+)

            BIT[po].lef=M-L++BIT[po*+].lef;

        if(BIT[po*+].rig==R-M)

            BIT[po].rig=R-M+BIT[po*].rig;

    }

}

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

{

    if(L==R)

    {

        BIT[po].lef=BIT[po].rig=BIT[po].mid=;

        scanf("%d",&COL[po]);

        BIT[po].x=BIT[po].y=COL[po];

        return;

    }

    int M=(L+R)/;

    COL[po]=;

    build_tree(lson);

    build_tree(rson);

    pushUP(L,R,po);

}

void update(int ul,int ur,int add,int L,int R,int po)

{

    if(ul<=L&&ur>=R)

    {

        COL[po]+=add;

        BIT[po].x+=add;

        BIT[po].y+=add;

        return;

    }

    pushDown(po);

    int M=(L+R)/;

    if(ul<=M)

        update(ul,ur,add,lson);

    if(ur>M)

        update(ul,ur,add,rson);

    pushUP(L,R,po);

}

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

{

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

        return BIT[po].mid;

    pushDown(po);

    int M=(L+R)/;

    int maxn;

    if(ql>M)

        return query(ql,qr,rson);

    else if(qr<=M)

        return query(ql,qr,lson);

    else

    {

        maxn=max(query(ql,qr,lson),query(ql,qr,rson));

        if(BIT[po*].y<BIT[po*+].x)

            maxn=max(maxn,min(M-ql+,BIT[po*].rig)+min(qr-M,BIT[po*+].lef));

        return maxn;

    }

}

int main()

{

    int T;

    char ch[];

    int a,b,c;

    cin>>T;

    for(int cas=;cas<=T;++cas)

    {

        printf("Case #%d:\n",cas);

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

        build_tree(,N,);

        for(int i=;i<=Q;++i)

        {

            scanf("%s",ch);

            if(ch[]=='q')

            {

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

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

            }

            else

            {

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

                update(a,b,c,,N,);

            }

        }

    }

    return ;

}

巴特西

(中等) UESTC 360 Another LCIS ，线段树+区间更新。

最新文章

热门文章