/*
分析:
线段树的区间合并果题。
犯了一个弱智错误,还检查了两天才检查出来,
这两天很没状态。。。
2012-10-26
*/
#include"stdio.h" #include"string.h" #include"stdlib.h" struct SegTree { int l,r,mid; int l_max,r_max,m_max; }T[400000]; int a[100011]; void pushup(int k) { int l_l,r_l; l_l=T[2*k].r-T[2*k].l+1; r_l=T[2*k+1].r-T[2*k+1].l+1; T[k].m_max=T[2*k].m_max>T[2*k+1].m_max?T[2*k].m_max:T[2*k+1].m_max; if(a[T[2*k].r]<a[T[2*k+1].l]) T[k].m_max=T[k].m_max>T[2*k].r_max+T[2*k+1].l_max?T[k].m_max:T[2*k].r_max+T[2*k+1].l_max; T[k].l_max=T[2*k].l_max; if(T[2*k].l_max==l_l && a[T[2*k].r]<a[T[2*k+1].l]) T[k].l_max+=T[2*k+1].l_max; T[k].r_max=T[2*k+1].r_max; if(T[2*k+1].r_max==r_l && a[T[2*k].r]<a[T[2*k+1].l]) T[k].r_max+=T[2*k].r_max; } void build(int l,int r,int k) { T[k].l=l; T[k].r=r; T[k].mid=(l+r)>>1; if(l==r) { T[k].l_max=T[k].r_max=T[k].m_max=1; return ; } build(l,T[k].mid,2*k); build(T[k].mid+1,r,2*k+1); pushup(k); } void update(int aim,int fresh,int k) { if(T[k].l==T[k].r && T[k].l==aim) { a[aim]=fresh; return ; } if(aim<=T[k].mid) update(aim,fresh,2*k); else update(aim,fresh,2*k+1); pushup(k); } int Query(int l,int r,int k) { int ans=0; int t1,t2; if(T[k].l==l && T[k].r==r) return T[k].m_max; if(r<=T[k].mid) ans=Query(l,r,2*k); else if(l>T[k].mid) ans=Query(l,r,2*k+1); else { t1=Query(l,T[k].mid,2*k); t2=Query(T[k].mid+1,r,2*k+1); ans=t1>t2?t1:t2; if(a[T[k].mid]<a[T[k].mid+1]) { t1=T[2*k].r_max>(T[k].mid-l+1)?(T[k].mid-l+1):T[2*k].r_max; t2=T[2*k+1].l_max>(r-T[k].mid)?(r-T[k].mid):T[2*k+1].l_max; ans=ans>(t1+t2)?ans:(t1+t2); } } return ans; } int main() { int T; int n,m; int i; char str[11]; int t1,t2; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) scanf("%d",&a[i]); build(0,n-1,1); while(m--) { scanf("%s",str); if(str[0]=='U') {scanf("%d%d",&t1,&t2);update(t1,t2,1);} else {scanf("%d%d",&t1,&t2);printf("%d\n",Query(t1,t2,1));} } } return 0; }