hdu3308 线段树——区间合并

更新一个点； 求某个区间的最长连续上升序列； 链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 100009
#define mid int m=(l+r)>>1
int num[maxn], lsum[maxn<<2], rsum[maxn<<2], msum[maxn<<2], n, m, p, v, a, b;
void pushup(int o, int l, int r)
{
    mid;
    if (num[m] < num[m+1])
    {
        lsum[o] = (lsum[o<<1] == m+1-l) ? (m+1-l+lsum[o<<1|1]) : lsum[o<<1];
        rsum[o] = (rsum[o<<1|1] == r-m) ? (r-m+rsum[o<<1]) : rsum[o<<1|1];
        msum[o] = max(max(msum[o<<1], msum[o<<1|1]), lsum[o<<1|1] + rsum[o<<1]);
    }
    else lsum[o] = lsum[o<<1], rsum[o] = rsum[o<<1|1], msum[o] = max(msum[o<<1], msum[o<<1|1]);
}
void build(int o, int l, int r)
{
    if (l == r) {lsum[o]= rsum[o] = msum[o] = 1; return;}
    mid; build(o<<1, l, m), build(o<<1|1, m+1, r), pushup(o, l, r);
}
void update(int o, int l, int r)
{
    if (l == r) {num[p] = v; return;}
    mid; if (p <= m) update(o<<1, l, m); else update(o<<1|1, m+1, r); pushup(o, l, r);
}
int query(int o, int l, int r)
{
    if (a <= l && b >= r) return msum[o];
    mid; int ret = 0;
    if (a <= m) ret = max(ret, query(o<<1, l, m)); if (b > m) ret = max(ret, query(o<<1|1, m+1, r));
    if (num[m] < num[m+1]) ret = max(ret, min(m-a+1, rsum[o<<1])+min(b-m, lsum[o<<1|1])); return ret;
}
int main(void)
{
    int t, n, m; char ch[5]; scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m); for (int i = 1; i <= n; scanf("%d", num+i++)); build(1, 1, n);
        while (m--)
        {
            scanf("%s%d%d", ch, &a, &b); a++, b++;
            if (ch[0] == 'Q') printf("%d\n", query(1, 1, n)); else p = a, v = b-1, update(1, 1, n);
        }
    }
    return 0;
}

。。