题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308

题意：给你n个数，m个操作。操作有两种：1.U x y 将数组第x位变为y   2. Q x y 问数组第x位到第y位连续最长子序列的长度。对于每次询问，输出一个答案

题解：一道简单的线段树区间合并，一般线段树的区间合并都会设lsum,rsum，表示左连续和右连续还有sum表示总共的连续。

转移比较复杂那这题为例

int L = T[i << 1].r , R = T[(i << 1) | 1].l;

    T[i].l = T[i << 1].l , T[i].r = T[(i << 1) | 1].r;

    T[i].lsum = T[i << 1].lsum , T[i].rsum = T[(i << 1) | 1].rsum;

    T[i].sum = max(T[i << 1].sum , T[(i << 1) | 1].sum);

    if(a[L] < a[R] && R - L == 1) {

        if(T[i << 1].lsum == T[i << 1].r - T[i << 1].l + 1) {

            T[i].lsum += T[(i << 1) | 1].lsum;

        }//注意看是否可以合并

        if(T[(i << 1) | 1].rsum == T[(i << 1) | 1].r - T[(i << 1) | 1].l + 1) {

            T[i].rsum += T[i << 1].rsum;

        }//注意看是否可以合并

        T[i].sum = max(T[i].sum , T[i << 1].rsum + T[(i << 1) | 1].lsum);

    }

区间合并注意T[i].lsum的更新和T[i].rsum的更新，sum的更新比较简单。

#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 1e5 + 10;int a[M];struct TnT {    int l , r , lsum , rsum , sum;}T[M << 2];void push_up(int i) {    int L = T[i << 1].r , R = T[(i << 1) | 1].l;    T[i].l = T[i << 1].l , T[i].r = T[(i << 1) | 1].r;    T[i].lsum = T[i << 1].lsum , T[i].rsum = T[(i << 1) | 1].rsum;    T[i].sum = max(T[i << 1].sum , T[(i << 1) | 1].sum);    if(a[L] < a[R] && R - L == 1) {        if(T[i << 1].lsum == T[i << 1].r - T[i << 1].l + 1) {            T[i].lsum += T[(i << 1) | 1].lsum;        }        if(T[(i << 1) | 1].rsum == T[(i << 1) | 1].r - T[(i << 1) | 1].l + 1) {            T[i].rsum += T[i << 1].rsum;        }        T[i].sum = max(T[i].sum , T[i << 1].rsum + T[(i << 1) | 1].lsum);    }}void build(int l , int r , int i) {    int mid = (l + r) >> 1;    T[i].l = l , T[i].r = r , T[i].lsum = 1 , T[i].rsum = 1 , T[i].sum = 1;    if(l == r) return ;    build(l , mid , i << 1);    build(mid + 1 , r , (i << 1) | 1);    push_up(i);}void updata(int pos , int ad , int i) {    int mid = (T[i].l + T[i].r) >> 1;    if(T[i].l == pos && T[i].r == pos) {        a[pos] = ad;        return ;    }    if(mid < pos) updata(pos , ad , (i << 1) | 1);    else updata(pos , ad , i << 1);    push_up(i);}int query(int l , int r , int i) {    int mid = (T[i].l + T[i].r) >> 1;    if(T[i].l == l && T[i].r == r) {        return T[i].sum;    }    push_up(i);    if(mid < l) {        return query(l , r , (i << 1) | 1);    }    else if(mid >= r) {        return query(l , r , i << 1);    }    else {        int ans = max(query(l , mid , i << 1) , query(mid + 1 , r , (i << 1) | 1));        ans = max(ans , 1);        if(a[T[i << 1].r] < a[T[(i << 1) | 1].l] && T[i].l != T[i].r) {            return max(ans , min(T[i << 1].rsum , mid - l + 1) + min(T[(i << 1) | 1].lsum , r - mid));        }        else {            return ans;        }    }}int main() {    int t , n , m , x , y;    scanf("%d" , &t);    while(t--) {        scanf("%d%d" , &n , &m);        for(int i = 0 ; i < n ; i++) {            scanf("%d" , &a[i]);        }        char cp[10];        build(0 , n , 1);        while(m--) {            scanf("%s" , cp);            scanf("%d%d" , &x , &y);            if(cp[0] == ‘U‘) {                updata(x , y , 1);            }            else {                printf("%d\n" , query(min(x , y) , max(x , y) , 1));            }        }    }    return 0;}

hdu 3308 LCIS（线段树区间合并）