学步园

题意：给定n个数，然后对这n个数进行m次操作。一种操作是将第A个数替换成B，另一种操作是询问区间[a,b]是的最长连续递增子序列的长度。

分析：每个节点分别记录包括左端点的LCIS、包括右端点的LCIS和区间上的LCIS。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100010;
int val[maxn];
int lnum[maxn<<2], rnum[maxn<<2], mnum[maxn<<2]; // 左边最长、右边最长和区间最长

void pushUp(int l, int r, int rt)
{
    lnum[rt] = lnum[rt<<1];
    rnum[rt] = rnum[rt<<1|1];
    mnum[rt] = max(mnum[rt<<1], mnum[rt<<1|1]);
    int m = (l + r) >> 1;
    if (val[m] < val[m+1]) // 这个地方要特别注意
    {
        if (lnum[rt] == m - l + 1)
            lnum[rt] += lnum[rt<<1|1];
        if (rnum[rt] == r - m)
            rnum[rt] += rnum[rt<<1];
        mnum[rt] = max(mnum[rt], rnum[rt<<1] + lnum[rt<<1|1]);
    }
}

void build(int l, int r, int rt)
{
    if (l == r)
    {
        lnum[rt] = rnum[rt] = mnum[rt] = 1;
        return ;
    }
    int m = (l + r) >> 1;
    if (l <= m) build(l, m, rt << 1);
    if (r > m) build(m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
    return ;
}

void update(int p, int c, int l, int r, int rt)
{
    if (l == r)
    {
        val[l] = c;
        return ;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, c, l, m, rt << 1);
    else update(p, c, m + 1, r, rt << 1 | 1);
    pushUp(l, r, rt);
    return ;
}

int query(int L, int R, int l, int r, int rt)
{
    if (L == l && R == r)
        return mnum[rt];
    int m = (l + r) >> 1;
    if (R <= m) return query(L, R, l, m, rt << 1);
    if (L > m) return query(L, R, m + 1, r, rt << 1 | 1);
    else
    {
        // a为在左孩子节点中查询到的区间[L,m]上的LCIS
        // b为在有孩子节点中查询到的区间[m+1,R]上的LCIS
        // c为跨越左右孩子节点的区间[L,R]上的LCIS
        int a = query(L, m, l, m, rt << 1);
        int b = query(m + 1, R, m + 1, r, rt << 1 | 1);
        int c = 0;
        if (val[m] < val[m+1])
        {
            c += min(rnum[rt<<1], m - L + 1);
            c += min(lnum[rt<<1|1], R - m);
        }
        return max(a, max(b, c));
    }
}

int main()
{
    int t, n, m;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i)
            scanf("%d", &val[i]);
        build(0, n - 1, 1);
        char op[2];
        int a, b;
        while (m--)
        {
            scanf("%s %d %d", op, &a, &b);
            if (op[0] == 'Q')
                printf("%d\n", query(a, b, 0, n - 1, 1));
            else update(a, b, 0, n - 1, 1);
        }
    }
    return 0;
}