原题传送：

　　线段树，区间合并。

　　节点记录下面变量：

　　int l, r, c;   // 区间左端点、右端点和区间长度

　　int lv, rv;    // 区间左值，右值

　　int lsum, rsum, msum;  // 区间左上升长度，右上升长度，区间最大上升长度

 

1 #include 
      
         2 #include 
       
          3 #define lson (cur << 1)  4 #define rson (cur << 1 | 1)  5 #define N 100010  6   7 int n, m, a[N];  8   9 inline int max(int x, int y){
    return x > y ? x : y;} 10 inline int min(int x, int y){
    return x < y ? x : y;} 11  12 struct node 13 { 14     int l, r, c;           // 区间左端点、右端点和区间长度 15     int lv, rv;            // 区间左值，右值 16     int lsum, rsum, msum;  // 区间左上升长度，右上升长度，最大上升长度 17 }tree[N << 2]; 18  19 void pushup(int cur) 20 { 21     tree[cur].lv = tree[lson].lv; 22     tree[cur].rv = tree[rson].rv; 23     tree[cur].lsum = tree[lson].lsum; 24     tree[cur].rsum = tree[rson].rsum; 25     tree[cur].msum = max(tree[lson].msum, tree[rson].msum); 26     if(tree[lson].rv < tree[rson].lv) 27     { 28         if(tree[lson].lsum == tree[lson].c && tree[lson].rv < tree[rson].lv) 29             tree[cur].lsum += tree[rson].lsum; 30         if(tree[rson].rsum == tree[rson].c && tree[rson].lv > tree[lson].rv) 31             tree[cur].rsum += tree[lson].rsum; 32          33         tree[cur].msum = max(tree[cur].msum, tree[lson].rsum + tree[rson].lsum); 34     } 35 } 36  37 void update(int cur, int loc, int v) 38 { 39     if(tree[cur].l == tree[cur].r) 40     { 41         tree[cur].lv = tree[cur].rv = v; 42         return ; 43     } 44     int mid = (tree[cur].l + tree[cur].r) >> 1; 45     if(mid >= loc) 46         update(lson, loc, v); 47     else 48         update(rson, loc, v); 49     pushup(cur); 50 } 51  52 int query(int cur, int l, int r) 53 { 54     if(tree[cur].l >= l && tree[cur].r <= r){ 55         return tree[cur].msum; 56     } 57     int mid = (tree[cur].l + tree[cur].r) >> 1; 58     int ans = 0; 59     if(mid >= l) ans = max(ans, query(lson, l, r)); 60     if(mid < r) ans = max(ans, query(rson, l, r)); 61     if(tree[lson].rv < tree[rson].lv){ 62         ans = max(ans, min(mid - l + 1, tree[lson].rsum) + min(r - mid, tree[rson].lsum)); 63     } 64     return ans; 65 } 66  67 void build(int cur, int l, int r) 68 { 69     tree[cur].l = l, tree[cur].r = r, tree[cur].c = r - l + 1; 70     if(l == r) 71     { 72         tree[cur].lv = tree[cur].rv = a[l]; 73         tree[cur].lsum = tree[cur].rsum = tree[cur].msum = 1; 74         return ; 75     } 76     int mid = (l + r) >> 1; 77     build(lson, l, mid); 78     build(rson, mid + 1, r); 79     pushup(cur); 80 } 81  82 int main() 83 { 84     int cas, i, x, y; 85     char op[5]; 86     scanf("%d", &cas); 87     while(cas --) 88     { 89         scanf("%d%d", &n, &m); 90         for(i = 1; i <= n; i ++) 91             scanf("%d", &a[i]); 92         build(1, 1, n); 93         while(m --) 94         { 95             scanf("%s%d%d", op, &x, &y); 96             if(op[0] == 'Q') 97             { 98                 printf("%d\n", query(1, x + 1, y + 1)); 99             }100             else if(op[0] == 'U')101             {102                 update(1, x + 1, y);103             }104         }105     }106     return 0;107 }