HDOJ 3308 LCIS （线段树）

时间：2023-05-07 18:28:50

题目：

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<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
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

思路：

单点更新 区间查询求最长连续上升子序列

这题的重点在于区间合并

线段树维护的值有三个 区间左端点开始的最长连续长度lsum 区间右端点结束的最长连续长度 区间内最长连续长度

在向上更新的部分 要考虑一个特殊情况 即左儿子的右端点值小于右儿子的左端点值 代表至少在这两个点上是连续上升的

此时 如果左儿子的lsum大于左儿子的区间长度 代表左儿子的左端点开始的连续上升区间是左儿子的整个区间加上右儿子的左端点开始的连续上升区间 对这两个区间进行合并

同理 如果右儿子的rsum大于右儿子的区间长度 代表右儿子的右端点结束的连续上升区间是右儿子的整个区间加上左儿子的右端点结束的连续上升区间 对这两个区间进行合并

最后在进行区间查询的时候 如果左儿子的右端点值小于右儿子的左端点值 则还要考虑这两个区间加起来的情况 是否存在更长的连续上升区间

代码：
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int maxn=1e5+;

int n,m,a,b,t,ans;

int x[maxn];

char op[];

struct node{

    int l,r; //左右边界与连续的长度

    int ls,rs; //左右边界的值

    int lsum,rsum,sum; //左右最大LCIS 区间最大LCIS

}tree[maxn*];

void pushup(int rt){

    tree[rt].ls=tree[rt*].ls;

    tree[rt].rs=tree[rt*+].rs;

    tree[rt].lsum=tree[rt*].lsum;

    tree[rt].rsum=tree[rt*+].rsum;

    tree[rt].sum=max(tree[rt*].sum,tree[rt*+].sum);

    if(tree[rt*].rs<tree[rt*+].ls){//如果左子树的右边界值小于右子树的左边界值 合并左子树的右边界和右子树的左边界进行计算

        if(tree[rt*].lsum==(tree[rt*].r-tree[rt*].l+)){

            tree[rt].lsum+=tree[rt*+].lsum;

        }

        if(tree[rt*+].rsum==(tree[rt*+].r-tree[rt*+].l+)){

            tree[rt].rsum+=tree[rt*].rsum;

        }

        tree[rt].sum=max(tree[rt].sum,tree[rt*].rsum+tree[rt*+].lsum);

    }

}

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

    tree[rt].l=l;

    tree[rt].r=r;

    if(l==r){

        tree[rt].lsum=tree[rt].rsum=tree[rt].sum=;

        tree[rt].ls=tree[rt].rs=x[l];

        return;

    }

    int mid=(l+r)/;

    build(l,mid,rt*);

    build(mid+,r,rt*+);

    pushup(rt);

}

void update(int rt){

    if(tree[rt].l==tree[rt].r){

        tree[rt].ls=tree[rt].rs=b;

        return;

    }

    int mid=(tree[rt].l+tree[rt].r)/;

    if(a<=mid) update(rt*);

    else update(rt*+);

    pushup(rt);

}

int query(int rt){

    if(tree[rt].l>=a && tree[rt].r<=b){

        return tree[rt].sum;

    }

    int mid=(tree[rt].l+tree[rt].r)/;

    int ans=;

    if(a<=mid) ans=max(ans,query(rt*));

    if(b>mid) ans=max(ans,query(rt*+));

    if(tree[rt*].rs<tree[rt*+].ls)

        ans=max(ans,min(mid-a+,tree[rt*].rsum)+min(b-mid,tree[rt*+].lsum));

    return ans;

}

int main(){

 //   freopen("data.in","r",stdin);

 //   freopen("2.out","w",stdout);

    scanf("%d",&t);

    for(int id=;id<=t;id++){

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

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

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

        }

        build(,n,);

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

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

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

                a++;

                update();

            }

            if(op[]=='Q'){

                a++;b++;

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

            }

        }

    }

    return ;

}

相关文章