hdu 3308 LCIS(线段树单点更新+区间合并)中等难度的题目

阅读量：4036 次

发布时间：2019-05-24

本文共 2422 字，大约阅读时间需要 8 分钟。

1、

2、题目大意：

给出一个由n个数字组成的序列，有两种操作，U A B是将A位置的数字替换成B，Q A B是查询A-B区间有多少个递增的数字，也就是求A-B区间的最长上升子序列的长度

这道题目有对区间的查询及对单点的更新，很容易想到线段树，只是在具体实现的时候还是有些困难，具体看代码

要记录区间里的最长的序列长度是多少，用smax来记录。由于最长的连续上升序列可以在区间的左端点，右端点，所以在线段树里增加两个域lmax和rmax，分别表示，在区间的端点处，分别向右向左的最长的满足条件的序列长度。

在更新当前区间的lmax时，如果左子区间的lmax等于左子区间的长度，那么当前区间的lmax就要加上右儿子的lmax。更新当前区间的rmax时同理。

另外在查询的时候，要注意，有可能当前区间的lmax大于mid-st+1，所以要在其中取一个较小值，同理rmax有可能大于ed-mid。

3、题目：

LCIS

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3479 Accepted Submission(s): 1554

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

⁵)

Q A B(0<=A<=B< n).

Output

For each Q, output the answer.

Sample Input

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

Sample Output

11423125

Author

shǎ崽

Source

Recommend

wxl | We have carefully selected several similar problems for you:

4、AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 400005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int lmax[N],rmax[N],smax[N];int a[N];void pushUp(int d,int m,int rt){    lmax[rt]=lmax[rt<<1];    rmax[rt]=rmax[rt<<1|1];    smax[rt]=max(smax[rt<<1],smax[rt<<1|1]);    if(a[m]
      
       >1)))        lmax[rt]+=lmax[rt<<1|1];        if(rmax[rt<<1|1]==(d>>1))        rmax[rt]+=rmax[rt<<1];        smax[rt]=max(smax[rt],rmax[rt<<1]+lmax[rt<<1|1]);    }}void build(int l,int r,int rt){    if(l==r)    {        scanf("%d",&a[l]);        lmax[rt]=1;        rmax[rt]=1;        smax[rt]=1;        return ;    }    int m=(l+r)>>1;    build(lson);    build(rson);    pushUp(r-l+1,m,rt);}void update(int b,int c,int l,int r,int rt){    if(l==r)    {        a[b]=c;        return ;    }    int m=(l+r)>>1;    if(b<=m)    update(b,c,lson);    //错在if(r>m)    else    update(b,c,rson);    pushUp(r-l+1,m,rt);}int query(int L,int R,int l,int r,int rt){    if(L<=l && R>=r)    {        return smax[rt];    }    int m=(l+r)>>1;    int ans=-1;    if(L<=m)    ans=max(ans,query(L,R,lson));    if(R>m)    ans=max(ans,query(L,R,rson));    if(a[m]

转载地址：http://pwcdi.baihongyu.com/

你可能感兴趣的文章