HDU 3308 LCIS

题意：

U A B: 把第A个数变成B

Q A B: 输出【A，B】最长连续上升子序列（注意是连续  相当于子串）

思路：单点更新 ，区间合并几下左边开头最小  和右边结束最大的两个数即可。

 

#include
#include
#include
#include
#include 
#define lson (i<<1)
#define rson (i<<1|1)
#define N 100050
using namespace std;
int lsum[N*4],rsum[N*4],msum[N*4];
int lmaxn[N*4],rmaxn[N*4];
int a[N];
int max(int x,int y)
{return x>y?x:y;
}
int min(int x,int y)
{return xx:y;
}
void pushup(int i,int l,int r)
{int mid=(l+r)>>1;lsum[i]=lsum[lson];rsum[i]=rsum[rson];if(lsum[i]==mid-l+1&&rmaxn[lson]<lmaxn[rson])lsum[i]+=lsum[rson];if(rsum[i]==r-mid&&rmaxn[lson]<lmaxn[rson])rsum[i]+=rsum[lson];msum[i]=max(msum[lson],msum[rson]);if(rmaxn[lson]<lmaxn[rson])msum[i]=max(msum[i],rsum[lson]+lsum[rson]);lmaxn[i]=lmaxn[lson];rmaxn[i]=rmaxn[rson];
}
void build(int l,int r,int i)
{if(l==r){lsum[i]=rsum[i]=msum[i]=1;
lmaxn[i]=rmaxn[i]=a[l];return ;}int mid=(l+r)>>1;build(l,mid,lson);build(mid+1,r,rson);pushup(i,l,r);
}
void update(int l,int r,int p,int va,int i)
{if(l==r){lmaxn[i]=rmaxn[i]=va;return ;}int mid=(l+r)>>1;if(p<=mid)update(l,mid,p,va,lson);else update(mid+1,r,p,va,rson);pushup(i,l,r);
}
int query(int l,int r,int pl,int pr,int i)
{if(l>=pl&&r<=pr){return msum[i];}int mid=(l+r)>>1;if(pr<=mid)return query(l,mid,pl,pr,lson);else if(pl>mid)return query(mid+1,r,pl,pr,rson);else{int maxn1=0,maxn2=0;maxn1=query(l,mid,pl,mid,lson);maxn2=query(mid+1,r,mid+1,pr,rson);maxn1=max(maxn1,maxn2);if(rmaxn[lson]<lmaxn[rson]){int tmp=min(rsum[lson],mid-pl+1)+min(lsum[rson],pr-mid);maxn1=max(maxn1,tmp);}return maxn1;}
}
int main() {int tt,n,m;scanf("%d",&tt);while(tt--){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&a[i]);build(1,n,1);while(m--){char c;int l,r;scanf(" %c%d%d",&c,&l,&r);if(c=='U'){l++;update(1,n,l,r,1);}else{l++;r++;printf("%d
",query(1,n,l,r,1));}}}return 0;
}