LCIS

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6069 Accepted Submission(s): 2635

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].

Input

T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10⁵).
The next line has n integers(0<=val<=10⁵).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10⁵)
OR
Q A B(0<=A<=B< n).

Output

For each Q, output the answer.

Sample Input

1
10 10
7 7 3 3 5 9 9 8 1 8
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9

Sample Output

1
1
4
2
3
1
2
5

题意：求解区间 a - b之内的最大连续上升子序列

题解：线段树区间合并 ,主要是PushUp操作和查询操作 ,在线段树中最长子序列可能在左子树也可能在右子树，也可能从左子树到右子树

,所以我们在在树的结构体中增加三个变量(左边的最长区间，右边的最长区间，最长合区间).然后其余的详细解释都在代码中了，有兴趣的朋友可以

看看.主要是理解左子树的右子树和右子树的左子树是如何影响区间的合区间，然后查询操作一定要记得不要超过查询区间了。

#include<iostream>

#include<cstdio>

#define N 100005

using namespace std;

int MAX(int i,int j){

    if(i>j) return i;

    return j;

}

int MIN(int i,int j){

    if(i<j) return i;

    return j;

}

struct Tree{

    int l,r;

    int lv,rv,mv;  ///lv(rv)表示从最左(右)边起的最长连续递增子序列长度,mv表示该区间最大频率

}tree[*N];

int a[N];

void PushUp(int l,int r,int idx){

    tree[idx].lv = tree[idx<<].lv;  ///默认为左儿子的lv

    tree[idx].rv = tree[idx<<|].rv; ///默认为右儿子的rv

    tree[idx].mv = MAX(tree[idx<<].mv,tree[idx<<|].mv);///对于父区间的mv值，默认是先在左右子区间的mx值中取一个较大值

    int mid=(l+r)>>;

    int len = r-l+;  ///区间长度

    if(a[mid]<a[mid+]){ ///两边可以进行合并

        ///如果左子区间的lv等于左子区间的长度且可以延伸到右子区间,那么父区间的lv值等于左子区间

        ///的lv加上右子区间的lv，否则，父区间的lv值就是左子区间的lv值，对于右子区间，同理

        if(tree[idx].lv==len-(len>>)) tree[idx].lv +=tree[idx<<|].lv;

        if(tree[idx].rv==(len>>)) tree[idx].rv +=tree[idx<<].rv;

        ///果左右区间能够延续，则在当前值和左子区间的rv+右子区间的lv之间取较大值

        tree[idx].mv = MAX(tree[idx].mv,tree[idx<<].rv+tree[idx<<|].lv);

    }

}

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

    tree[idx].l = l;

    tree[idx].r = r;

    if(l==r){

        tree[idx].lv = tree[idx].rv = tree[idx].mv = ;

        return;

    }

    int mid = (l+r)>>;

    build(l,mid,idx<<);

    build(mid+,r,idx<<|);

    PushUp(l,r,idx);

}

void update(int l,int r,int pos,int idx){ ///单点更新

    if(l==r) {

        return;

    }

    int mid=(l+r)>>;

    if(pos<=mid) update(l,mid,pos,idx<<);

    else update(mid+,r,pos,idx<<|);

    PushUp(l,r,idx);

}

int query(int l,int r,int idx){

    if(tree[idx].l>=l&&tree[idx].r<=r){

        return tree[idx].mv;

    }

    int mid=(tree[idx].l+tree[idx].r)>>;

    int ans = ;

    ///分别在左子区间和右子区间查找，结果分别为x,y,如果左右两个区间不能延续，

    ///那肯定是在x,y中找一个最大值

    if(l<=mid) ans = MAX(ans,query(l,r,idx<<)); ///x

    if(r>mid) ans = MAX(ans,query(l,r,idx<<|)); ///y

    ///如果能够延续,设两端延续区间长度为z,那么肯定是在 x,y,z找最大值，另外，对于左区间,我们要保证

    ///向左延续的区间(rv)肯定是在[l,mid]中的(不然超过我们要查询的区间了),所以长度必须要在 mid - l+1之内

    ///向右亦如此.

    if(a[mid]<a[mid+]){

        ans = MAX(ans,MIN(mid-l+,tree[idx<<].rv)+MIN(r-mid,tree[idx<<|].lv)); ///z

    }

    return ans;

}

int main()

{

    int n,m;

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

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

       for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

       }

       build(,n,);

       //for(int i=1;i<=n;i++) printf("%d ",tree[i].mv);

       //printf("\n");

       while(m--){

            char s[];

            scanf("%s",s);

            if(s[]=='U'){

                int b,c;

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

                a[++b] = c;  ///由于题目下标从0开始，所以++

                update(,n,b,);

            }else {

                int b,c;

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

                b++,c++;

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

            }

       }

    }

    return ;

}

秒客网

hdu 3308(线段树区间合并)

LCIS

相关文章