1 #include <set>  2 #include <map>  3 #include <cmath>  4 #include <ctime>  5 #include <queue>  6 #include <stack>  7 #include <cctype>  8 #include <cstdio>  9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 typedef unsigned long long ull; 17 typedef long long ll; 18 const int inf = 0x3f3f3f3f; 19 const double eps = 1e-8; 20 template <class T> 21 inline bool scan_d(T &ret) 22 { 23     char c; 24     int sgn; 25     if(c=getchar(),c==EOF) return 0; 26     while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) 27         c=getchar(); 28     sgn=(c==‘-‘)?-1:1; 29     ret=(c==‘-‘)?0:(c-‘0‘); 30     while(c=getchar(),c>=‘0‘&&c<=‘9‘) 31         ret=ret*10+(c-‘0‘); 32     ret*=sgn; 33     return 1; 34 } 35  36 const int maxn = 1e5+10; 37 int ls[maxn<<2],rs[maxn<<2];       //ls为区间左值，rs为区间右值  比较时要用到。 38 int lsum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];  //lsum为区间左上升长度，rsum为区间右上升长度，sum为区间最大上升长度。 39  40 void push_up(int l,int r,int pos) 41 { 42     ls[pos] = ls[pos<<1]; 43     rs[pos] = rs[pos<<1|1]; 44     lsum[pos] = lsum[pos<<1]; 45     rsum[pos] = rsum[pos<<1|1]; 46     sum[pos] = max(sum[pos<<1],sum[pos<<1|1]); 47     int mid = (l + r) >> 1; 48     if (ls[pos<<1|1] > rs[pos<<1]) 49     { 50         sum[pos] = max(sum[pos],rsum[pos<<1] + lsum[pos<<1|1]); 51         if (lsum[pos<<1] == mid - l + 1)               //左区间左上升长度已满 52             lsum[pos] += lsum[pos<<1|1]; 53         if (rsum[pos<<1|1] == r - mid)                 //同理， 54             rsum[pos] += rsum[pos<<1]; 55     } 56 } 57  58 void build (int l,int r,int pos) 59 { 60     if (l == r) 61     { 62         int tmp; 63         scanf ("%d",&tmp); 64         ls[pos] = tmp; 65         rs[pos] = tmp; 66         lsum[pos] = rsum[pos] = sum[pos] = 1; 67         return; 68     } 69     int mid =(l + r) >> 1; 70     build(l,mid,pos<<1); 71     build(mid+1,r,pos<<1|1); 72     push_up(l,r,pos); 73 } 74  75 void update(int l,int r,int pos,int x,int val) 76 { 77     if (l == r) 78     { 79         ls[pos] = rs[pos] = val; 80         return; 81     } 82     int mid = (l + r) >> 1; 83     if (x <= mid) 84         update(l,mid,pos<<1,x,val); 85     else 86         update(mid+1,r,pos<<1|1,x,val); 87     push_up(l,r,pos); 88 } 89  90  91 int query(int l,int r,int pos,int ua,int ub) 92 { 93     if (ua <= l && ub >= r) 94     { 95         return sum[pos]; 96     } 97     int mid = (l + r) >> 1; 98     int ans1 = 0,ans2 = 0,ans3 = 0; 99     if (ua <= mid)100         ans1 = query(l,mid,pos<<1,ua,ub);101     if (ub > mid)102         ans2 = query(mid+1,r,pos<<1|1,ua,ub);103     if (ls[pos<<1|1] > rs[pos<<1])104         ans3 = min(lsum[pos<<1|1],ub-mid) + min(rsum[pos<<1],mid-ua+1);105     return max(ans1,max(ans2,ans3));106 }107 108 109 int main(void)110 {111     #ifndef ONLINE_JUDGE112     freopen("in.txt","r",stdin);113     #endif114     int t;115     cin>>t;116     while (t--)117     {118         int n,q;119         scanf ("%d%d",&n,&q);120         build(1,n,1);121         char op[10];122         int x,y;123         for (int i = 0; i < q; i++)124         {125             scanf ("%s%d%d",op,&x,&y);126             if (op[0] == ‘Q‘)127                 printf("%d\n",query(1,n,1,x+1,y+1));128             if (op[0] == ‘U‘)129                 update(1,n,1,x+1,y);130         }131     }132     return 0;133 }