线段树求最长连续上升子序列

//#include <bits/stdc++.h>

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct Node
{
    int Pre, Suf;
    int PreSize, SufSize, SumSize, Size;
    int Left, Right;
};

struct Node SegTree[100005];
int c[100005] = {0};


void Built(int k, int L, int R)
{
    SegTree[k].Left = L;
    SegTree[k].Right = R;
    if(SegTree[k].Left == SegTree[k].Right)
    {
        SegTree[k].Pre = SegTree[k].Suf = c[L];
        SegTree[k].PreSize = SegTree[k].SufSize = SegTree[k].SumSize = SegTree[k].Size = 1;
        return;
    }

    int Mid = (SegTree[k].Left + SegTree[k].Right) >> 1;

    Built(k<<1, L, Mid);

    Built(k<<1 | 1, Mid+1, R);

    SegTree[k].Pre = SegTree[k<<1].Pre;

    SegTree[k].Suf = SegTree[k<<1 |1 ].Suf;

    SegTree[k].PreSize = SegTree[k<<1].PreSize;
    if(SegTree[k<<1].PreSize == SegTree[k<<1].SumSize
       && SegTree[k<<1].Suf < SegTree[k<<1 | 1].Pre)
        SegTree[k].PreSize += SegTree[k<<1 | 1].PreSize;

    SegTree[k].SufSize = SegTree[k<<1 | 1].SufSize;
    if(SegTree[k<<1 | 1].SufSize == SegTree[k<<1 | 1].SumSize
       && SegTree[k<<1].Suf < SegTree[k<<1 | 1].Pre)
       SegTree[k].SufSize += SegTree[k<<1].SufSize;

    SegTree[k].SumSize = SegTree[k<<1].SumSize + SegTree[k<<1 | 1].SumSize;

    SegTree[k].Size = max(SegTree[k<<1].Size, SegTree[k<<1 | 1].Size);

    if(SegTree[k<<1].Suf < SegTree[k<<1 | 1].Pre)
        SegTree[k].Size = max(SegTree[k].Size, SegTree[k<<1].SufSize+SegTree[k<<1 | 1].PreSize);

}

void Updata(int k, int dir, int num)
{
    if(SegTree[k].Left == SegTree[k].Right)
    {
        SegTree[k].Pre = SegTree[k].Suf = num;
   //     cout << "U" << SegTree[k].Left << " " <<k << endl;
        return;
    }

    int Mid = (SegTree[k].Left+SegTree[k].Right) >> 1;

    if(dir <= Mid)
        Updata(k<<1, dir, num);
    if(dir > Mid)
        Updata(k<<1 | 1, dir, num);


    SegTree[k].Pre = SegTree[k<<1].Pre;

    SegTree[k].Suf = SegTree[k<<1 |1 ].Suf;

    SegTree[k].PreSize = SegTree[k<<1].PreSize;
    if(SegTree[k<<1].PreSize == SegTree[k<<1].SumSize
       && SegTree[k<<1].Suf < SegTree[k<<1 | 1].Pre)
        SegTree[k].PreSize += SegTree[k<<1 | 1].PreSize;

    SegTree[k].SufSize = SegTree[k<<1 | 1].SufSize;
    if(SegTree[k<<1 | 1].SufSize == SegTree[k<<1 | 1].SumSize
       && SegTree[k<<1].Suf < SegTree[k<<1 | 1].Pre)
       SegTree[k].SufSize += SegTree[k<<1].SufSize;

    SegTree[k].SumSize = SegTree[k<<1].SumSize + SegTree[k<<1 | 1].SumSize;

    SegTree[k].Size = max(SegTree[k<<1].Size, SegTree[k<<1 | 1].Size);

    if(SegTree[k<<1].Suf < SegTree[k<<1 | 1].Pre)
        SegTree[k].Size = max(SegTree[k].Size, SegTree[k<<1].SufSize+SegTree[k<<1 | 1].PreSize);
}

struct Node Query(int k, int L, int R)
{
    if(L <= SegTree[k].Left && SegTree[k].Right <= R)
        return SegTree[k];

    int Mid = (SegTree[k].Left+SegTree[k].Right) >> 1;

    struct Node ans,Node1,Node2;
    char tag1 = 0, tag2 = 0;

    if(L <= Mid)
    {
        Node1 = Query(k<<1, L, R);
        tag1 = 1;
    }

    if(Mid < R)
    {
        Node2 = Query(k<<1 | 1, L, R);
        tag2 = 1;
    }

    if(tag1 && tag2)
    {
        ans.Pre = Node1.Pre;

        ans.Suf = Node2.Suf;

        ans.PreSize = Node1.PreSize;
        if(Node1.PreSize == Node1.SumSize
           && Node1.Suf < Node2.Pre)
            ans.PreSize += Node2.PreSize;

        ans.SufSize = Node2.SufSize;
        if(Node2.SufSize == Node2.SumSize
           && Node1.Suf < Node2.Pre)
           ans.SufSize += Node1.SufSize;

        ans.SumSize = Node1.SumSize + Node2.SumSize;

        ans.Size = max(Node1.Size, Node2.Size);
        if(Node1.Suf < Node2.Pre)
            ans.Size = max(ans.Size, Node1.SufSize+Node2.PreSize);

    }else
    {
        ans = tag1 ? Node1 : Node2;
    }


    return ans;
}



int main(void)
{
//    freopen("G:\\in.txt","r", stdin);

    int T = 0;
 //   cin >> T;

    while(scanf("%d", &T) != EOF)
    {
        int M,N;

        while(T--)
        {
            //cin >> M >> N;
            scanf("%d%d", &M, &N);

            for(int i = 0; i < M; i++)
            {
                //cin >> c[i];
                scanf("%d", &c[i]);
            }

            Built(1, 0, M-1);

            while(N--)
            {
                char ch;
                int num1, num2;

             //   cin >> ch >> num1 >> num2;

             //   cin >> ch;

               // scanf("%c%d%d", &ch, &num1, &num2);

                if(ch == 'Q')
                {
                    cout << Query(1, num1, num2).Size << endl;
                }
                if(ch == 'U')
                {
                    Updata(1, num1, num2);
                }
            }

        }

    }

    return 0;
}