HDU 3308 LCIS（线段树的区间合并）

﹏ヽ暗。殇╰゛Y 2022-06-11 09:37 200阅读 0赞

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

题解：

一开始看到题目还以为是求公共最长上升子序列，感觉就很有难度，再看下题，尼玛才给一个序列怎么做。。然后就带着疑惑搜了题解

然后震惊了，原来题目要你求的是一个区间中序列中连续上升的最长长度，并不是特别难的区间合并，都是标题党惹的祸

题意：

给你个序列，给出n为范围\[0，n-1\],m为操作个数，输入'Q'再输入x，y表示询问\[x,y\]里面的最长连续上升子序列长度，'W'是将第x个的值换成y，就是区间合并的时候和询问的时候有一定的难度

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        int l,r;
        int maxl;//区间最长上升连续子序列长度
        int lms,rms;//区间从左，右数最长上升连续子序列长度
        int lv,rv;//保存区间左右端点的值
        int len()//区间长度
        {
            return r-l+1;
        }
    }t[100005*4];
    void pushup(int k)//区间合并
    {
        t[k].maxl=max(t[lson].maxl,t[rson].maxl);//日常更新
        t[k].lv=t[lson].lv;
        t[k].rv=t[rson].rv;
        t[k].lms=t[lson].lms;
        t[k].rms=t[rson].rms;
        if(t[lson].rv<t[rson].lv)//如果左子区间的右端点值小于右子区间的左端点值，可以合并
        {
            if(t[lson].lms==t[lson].len())//如果左子区间全为连续上升的，加上右子区间的左连续上升长度
                t[k].lms+=t[rson].lms;
            if(t[rson].rms==t[rson].len())//同理处理右区间
                t[k].rms+=t[lson].rms;
            t[k].maxl=max(t[k].maxl,t[lson].rms+t[rson].lms);//更新一波区间最大值
        }
    }
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        if(l==r)
        {
            scanf("%d",&t[k].lv);//直接在里面建树快得多
            t[k].rv=t[k].lv;
            t[k].maxl=t[k].lms=t[k].rms=1;//初始长度为1
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
        pushup(k);//一开始就要合并
    }
    void update(int pos,int k,int v)//简单的区间单点更新
    {
        if(t[k].l==t[k].r)
        {
            t[k].lv=t[k].rv=v;
            return;
        }
        int mid=M;
        if(pos<=mid)
            update(pos,lson,v);
        else
            update(pos,rson,v);
        pushup(k);
    }
    int query(int l,int r,int k)//询问
    {
        if(t[k].l==l&&t[k].r==r)
        {
            return t[k].maxl;
        }
        int mid=M;
        int p;
        if(r<=mid)
            p=query(l,r,lson);
        else if(l>mid)
            p=query(l,r,rson);
        else
        {
            p=max(query(l,mid,lson),query(mid+1,r,rson));
            if(t[lson].rv<t[rson].lv)//如果左子区间的右端点值小于右子区间的左端点值，更新长度
            {
                p=max(p,min(t[lson].rms,mid-l+1)+min(t[rson].lms,r-mid));//max右边部分为两个区间中间部分的最长连续长度，理解一下，不好说明
            }
        }
        return p;
    }
    int main()
    {
        int i,j,k,n,test,m,x,y;
        char s[10];
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d%d",&n,&m);
            Build(0,n-1,1);
            for(i=0;i<m;i++)
            {
                scanf("%s%d%d",s,&x,&y);
                if(s[0]=='Q')
                {
                    printf("%d\n",query(x,y,1));
                }
                else
                {
                    update(x,1,y);
                }
            }
        }
        return 0;
    }