线段树(区间合并) HDOJ 3308 LCIS

/************************************************
* Author        :Running_Time
* Created Time  :2015/9/25 星期五 10:37:34
* File Name     :G.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
struct ST   {
    struct Node {
        int lx, rx;
        int ls, rs, ms;
    }node[N<<2];
    void push_up(int l, int r, int rt)    {
        node[rt].ls = node[rt<<1].ls;   node[rt].rs = node[rt<<1|1].rs;
        node[rt].lx = node[rt<<1].lx;   node[rt].rx = node[rt<<1|1].rx;
        node[rt].ms = max (node[rt<<1].ms, node[rt<<1|1].ms);
        int mid = (l + r) >> 1;
        if (node[rt<<1].rx < node[rt<<1|1].lx)  {
            if (node[rt<<1].ls == mid - l + 1)  {
                node[rt].ls += node[rt<<1|1].ls;
            }
            if (node[rt<<1|1].rs == r - mid)    {
                node[rt].rs += node[rt<<1].rs;
            }
            node[rt].ms = max (node[rt].ms, node[rt<<1].rs + node[rt<<1|1].ls);
        }
    }
    void build(int l, int r, int rt)    {
        if (l == r) {
            scanf ("%d", &node[rt].lx);
            node[rt].rx = node[rt].lx;
            node[rt].ls = node[rt].rs = node[rt].ms = 1;
            return ;
        }
        int mid = (l + r) >> 1;
        build (lson);   build (rson);
        push_up (l, r, rt);
    }
    void updata(int p, int c, int l, int r, int rt) {
        if (l == r) {
            node[rt].lx = node[rt].rx = c;  return ;
        }
        int mid = (l + r) >> 1;
        if (p <= mid)   updata (p, c, lson);
        else    updata (p, c, rson);
        push_up (l, r, rt);
    }
    int query(int ql, int qr, int l, int r, int rt) {
        if (ql <= l && r <= qr) {
            return node[rt].ms;
        }
        int mid = (l + r) >> 1, ret = 0;
        if (ql <= mid)  {
            ret = max (ret, query (ql, qr, lson));
        }
        if (qr > mid)   {
            ret = max (ret, query (ql, qr, rson));
        }
        if (node[rt<<1].rx < node[rt<<1|1].lx)  {
            ret = max (ret, min (mid - ql + 1, node[rt<<1].rs) + min (qr - mid, node[rt<<1|1].ls));
        }
        return ret;
    }
}st;

int main(void)    {
    int T;  scanf ("%d", &T);
    while (T--)   {
        int n, q;   scanf ("%d%d", &n, &q);
        st.build (1, n, 1);
        for (int a, b, i=1; i<=q; ++i)    {
            char s[2];   scanf ("%s%d%d", &s, &a, &b);
            if (s[0] == ‘Q‘)  {
                printf ("%d\n", st.query (a + 1, b + 1, 1, n, 1));
            }
            else    {
                st.updata (a + 1, b, 1, n, 1);
            }
        }
    }

    return 0;
}