HDU3308：LCIS(线段树区间合并) - c++编程基础

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

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)

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

Output

For each Q, output the answer.

Sample Input

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

Q是询问区间内最大的LCIS

U是更新节点

思路：简单的线段树区间合并题

#include   
#include   
#include   
using namespace std;  
  
const int L = 111111;  
int n,m,s[L];  
  
struct node  
{  
    int l,r,c;//左右边界与连续的长度  
    int ln,rn;//左右边界的值  
    int ls,rs,ms,;//左右最大LCIS，和区间最大LCIS  
} a[L<<2];  
  
void pushup(int i)  
{  
    a[i].ls = a[2*i].ls;  
    a[i].rs = a[2*i+1].rs;  
    a[i].ln = a[2*i].ln;  
    a[i].rn = a[2*i+1].rn;  
    a[i].ms = max(a[2*i].ms,a[2*i+1].ms);  
    if(a[2*i].rn




>1;  
    init(l,mid,2*i);  
    init(mid+1,r,2*i+1);  
    pushup(i);  
}  
  
void insert(int i,int t,int m)  
{  
    if(a[i].l == a[i].r)  
    {  
        a[i].ln = a[i].rn = m;  
        return;  
    }  
    int mid = (a[i].l+a[i].r)>>1;  
    if(t<=mid)  
        insert(2*i,t,m);  
    if(t>mid)  
        insert(2*i+1,t,m);  
    pushup(i);  
}  
  
int query(int l,int r,int i)//查询最大的LCIS  
{  
    if(a[i].l>=l && a[i].r<=r)  
    {  
        return a[i].ms;  
    }  
    int mid = (a[i].l+a[i].r)>>1,ans = 0;  
    if(l<=mid)  
        ans = max(ans,query(l,r,2*i));  
    if(r>mid)  
        ans = max(ans,query(l,r,2*i+1));  
    if(a[2*i].rn < a[2*i+1].ln)  
        ans = max(ans , min(mid-l+1,a[2*i].rs)+min(r-mid,a[2*i+1].ls));  
    return ans;  
}  
  
  
int main()  
{  
    int t,i,l,r;  
    char str[5];  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d%d",&n,&m);  
        for(i = 1; i<=n; i++)  
            scanf("%d",&s[i]);  
        init(1,n,1);  
        while(m--)  
        {  
            scanf("%s%d%d",str,&l,&r);  
            if(str[0] == 'Q')  
                printf("%d\n",query(l+1,r+1,1));  
            else  
                insert(1,l+1,r);  
        }  
    }  
  
    return 0;  
}