5W次单点修改，求最长的连续上升子序列 HDU 3308

题目大意：给你n个数，m个操作。

有两种操作：

1.U x y 将数组第x位变为y

2. Q x y 问数组第x位到第y位连续最长子序列的长度。

对于每次询问，输出连续最长子序列的长度

思路：用线段树维护上升序列，每个端点维护：左边连续递增的len，右边连续递增的len，中间连续递增的len，左边val，右边val，和目前的len。然后不断更新即可。

注意：如果左区间的最右边的值小于右区间最左边的值，则有一个待定答案是左儿子的右区间+右儿子的左区间

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

/*

①记录本身内部的序列长度

②要将区间合并的时候，rightson的left区间和leftson的right区间判断条件以后再合并。

如果合并区间是对于两端的值

*/

const int maxn = 1e5 + ;

struct Tree{

    int leftlen, rightlen, midlen, leftval, rightval, len;

}tree[maxn << ];

int n, m;

inline void pushup(int o){

    int lb = o << , rb = o <<  | ;

    int lbval = tree[lb].rightval, rbval = tree[rb].leftval;

    bool flag = false;

    tree[o].midlen = max(tree[lb].rightlen, max(tree[rb].leftlen, max(tree[lb].midlen, tree[rb].midlen)));

    if (lbval < rbval) {

        flag = true;

        tree[o].midlen = max(tree[lb].rightlen + tree[rb].leftlen, tree[o].midlen);

    }

    tree[o].leftlen = tree[lb].leftlen;

    if (tree[lb].rightlen == tree[lb].len && flag) tree[o].leftlen = tree[o].midlen;

    tree[o].rightlen = tree[rb].rightlen;

    if (tree[rb].leftlen == tree[rb].len && flag) tree[o].rightlen = tree[o].midlen;

    tree[o].leftval = tree[lb].leftval, tree[o].rightval = tree[rb].rightval;

}

void buildtree(int l, int r, int o){

    tree[o].len = r - l + ;

    if (l == r){

        int val; scanf("%d", &val);

        tree[o].leftlen = tree[o].rightlen = tree[o].midlen = ;

        tree[o].leftval = tree[o].rightval = val;

        return ;

    }

    int mid = (l + r) / ;

    if (l <= mid) buildtree(l, mid, o << );

    if (r > mid) buildtree(mid + , r, o <<  | );

    pushup(o);

    //printf("l = %d r = %d leftlen = %d rightlen = %d midlen = %d\n", l, r, tree[o].leftlen, tree[o].rightlen, tree[o].midlen);

}

void update(int pos, int val, int l, int r, int o){

    if (pos == l && pos == r){

        tree[o].leftval = tree[o].rightval = val; return ;

    }

    int mid = (l + r) / ;

    if (pos <= mid) update(pos, val, l, mid, o << );

    if (pos > mid) update(pos, val, mid + , r, o <<  | );

    pushup(o);

}

int query(int ql, int qr, int l, int r, int o){

    int ans = ;

    if (ql <= l && qr >= r){

        ans = max(ans, max(tree[o].leftlen, max(tree[o].rightlen, tree[o].midlen)));

        return ans;

    }

    int mid = (l + r) / ;

    int t1 = -, t2 = -;

    if (mid >= ql){

        t1 = query(ql, qr, l, mid, o << );

    }

    if (mid < qr){

        t2 = query(ql, qr, mid + , r, o <<  | );

    }

    ans = max(ans, max(t1, t2));

    ///如果左区间的最右边的值小于右区间最左边的值，则有一个待定答案是左儿子的右区间+右儿子的左区间

    if (tree[o << ].rightval < tree[o <<  | ].leftval && t1 >  && t2 > ){

        t1 = min(tree[o << ].rightlen, mid - ql + ) + min(tree[o <<  | ].leftlen, qr - mid);

        ans = max(ans, t1);

    }

    return ans;

}

int main(){

    int t; cin >> t;

    while (t--){

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

        buildtree(, n, );

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

            char ch[]; int a, b;

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

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

                update(a + , b, , n, );

            }

            else {

                printf("%d\n", query(a + , b + , , n, ));

            }

        }

    }

    return ;

}

关键：

感觉和以前的一题CF很像，忘了是哪里的了......