最近开始线段树一段时间了，也发现了不少大牛的博客比如HH大牛 ，小媛姐。这个题目是我在看HH大牛的线段树专题是给出的习题，（可以去他博客找找，真心推荐）原本例题是POJ3667
Hotel 这个题目，是一个求连续空区间的情况，而hdoj这个题目是求给定区间单调连续的最大区间长度，两个题目思路很相似，将节点rt用sum[rt],lsum[rt],rsum[rt]来描述，分别表示rt对应区间即[l,r]内满足条件的区间的最大长度，从左边端点l开始满足条件的最大区间长度，从右边r开始向左的满足条件的最大区间长度。
void PushUp(int rt,int m,int mid)//mid表示更新区间的中点，m表示长度
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
int t=1;
if(A[mid]<A[mid+1])
{
if(lsum[rt]==(m-(m>>1)))
lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt]==(m>>1))
rsum[rt]+=rsum[rt<<1];
t= rsum[rt<<1]+lsum[rt<<1|1];
}
sum[rt]=max(t,max(sum[rt<<1],sum[rt<<1|1]));
}
PushUp函数和query函数是关键 ，PushUp函数向上更新时，先将lsum[rt]用
lsum[rt<<1]也就是左子区间左边开始的最大长度，如果这个区间长度刚好是l到mid之间的长度，说明区间已经穿过中点了，应该在加上右子区间lsum[rt<<1|1]这部分,类似的可以更新rsum[rt]。对于sum[rt]应该对应rsum[rt<<1]+lsum[rt<<1|1]，sum[rt<<1],sum[rt<<1|1]三种情况中的最大值，因为满足条件的最长单调区间可以是左半部分，右半部分，或者贯穿中点。
理解了这部分那么query函数可以按照类似的思路来写，但要注意的是对于贯穿中点的判断条件是A[mid]<A[mid+1]，这样才能将两部分加起来。
期间又一次犯二TLE了，原本是用C写的，max函数是用的宏定义，结果里面含有query函数，这样最终可能会两次调用query函数，不超时才怪，好在以前犯过一次，被基友发现了，改成algorithm里面的max就过了。哎，有个能debug基友就是好啊。hhha~
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 using namespace std;
int sum[N<<2],rsum[N<<2],lsum[N<<2],A[N]; void PushUp(int rt,int m,int mid)
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
int t=1;
if(A[mid]<A[mid+1])
{
if(lsum[rt]==(m-(m>>1)))
lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt]==(m>>1))
rsum[rt]+=rsum[rt<<1];
t= rsum[rt<<1]+lsum[rt<<1|1];
}
sum[rt]=max(t,max(sum[rt<<1],sum[rt<<1|1]));
} void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=lsum[rt]=rsum[rt]=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUp(rt,r-l+1,m);
} void update(int p,int l,int r,int rt)
{
if(l==r)
return;
int m=(l+r)>>1;
if(p<=m)
update(p,lson);
else update(p,rson);
PushUp(rt,r-l+1,m);
} int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return sum[rt];
}
int m=(l+r)>>1;
if(l==r)
return 1;
int ans=0;
if(R<=m)
ans=max(ans,query(L,R,lson));
else if(L>m)
ans=max(ans,query(L,R,rson));
else
{
ans=max(ans,query(L,R,lson));
ans=max(ans,query(L,R,rson));
int ll,rr;
if(m-L+1>=rsum[rt<<1])
ll=rsum[rt<<1];
else ll=m-L+1;
if(R-m>=lsum[rt<<1|1])
rr=lsum[rt<<1|1];
else rr=R-m;
ans=max(ans,ll);
ans=max(ans,rr);
if(A[m+1]>A[m])
ans=max(ans,ll+rr);
}
return ans;
} int main(void)
{
int T;
int n,m,a,b;
char op[3];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",A+i);
build(1,n,1);
while(m--)
{
scanf("%s%d%d",op,&a,&b);
if(op[0]=='U')
{
A[a+1]=b;
update(a+1,1,n,1);
}
else
{
int ans=query(a+1,b+1,1,n,1);
printf("%d\n",ans);
}
}
}
return 0;
}