LCIS
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10 5).
The next line has n integers(0<=val<=10 5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10 5)
OR
Q A B(0<=A<=B< n).
Output
For each Q, output the answer.
Sample Input
1
10 10
7 7 3 3 5 9 9 8 1 8
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9
Sample Output
1
1
4
2
3
1
2
5
题意：求区间[a,b]连续上升的最大区间长度。
解析：线段树维护以下几种信息：左右端点(le,ri),区间长度(len),左端的数(lenum),右端的数(rinum),从左边开始的最大连续上升子序列的长度(lelis),从右边开始的最大上升子序列的长度(rilis),该区间的最大连续上升子序列的长度(maxlen).具体操作见代码。
代码如下：
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<iterator>
#include<utility>
#include<sstream>
#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
const int INF=;
const double eps=0.00000001;
const int maxn=;
struct node
{
int le,ri,len;
int lenum,rinum;
int maxlis,lelis,rilis;
}tree[*maxn];
int elem[maxn];
void pushup(int id)
{
node& fa=tree[id]; //父亲
node& lson=tree[id*]; // 左儿子
node& rson=tree[id*+]; //右儿子
fa.lelis=lson.lelis, fa.rilis=rson.rilis; //更新
fa.lenum=lson.lenum, fa.rinum=rson.rinum;
fa.maxlis=max(lson.maxlis,rson.maxlis); //左右儿子中的最大值
if(lson.rinum<rson.lenum) //如果中间可以形成上升的连续的一段
{
if(lson.lelis==lson.len) fa.lelis+=rson.lelis; //可扩展
if(rson.rilis==rson.len) fa.rilis+=lson.rilis;
fa.maxlis=max(fa.maxlis,lson.rilis+rson.lelis); //最大值更新
}
}
void build_tree(int le,int ri,int id)
{
node& t=tree[id];
t.le=le,t.ri=ri,t.len=ri-le+;
if(le==ri)
{
t.lenum=t.rinum=elem[le];
t.maxlis=t.lelis=t.rilis=;
return;
}
int mid=(le+ri)/;
build_tree(le,mid,id*);
build_tree(mid+,ri,id*+);
pushup(id);
}
int query(int x,int y,int id)
{
if(tree[id].le>=x&&tree[id].ri<=y)
{
return tree[id].maxlis;
}
int mid=(tree[id].le+tree[id].ri)/;
int ret=;
if(x<=mid) ret=max(ret,query(x,y,id*)); //左边
if(y>mid) ret=max(ret,query(x,y,id*+));// 右边
if(tree[id*].rinum<tree[id*+].lenum) ret=max(ret,min(mid-x+,tree[id*].rilis)+min(y-mid,tree[id*+].lelis));//中间
return ret;
}
void update(int id,int pos,int val)
{
if(tree[id].le==tree[id].ri)
{ tree[id].lenum=tree[id].rinum=val; //单点更新
return;
}
int mid=(tree[id].le+tree[id].ri)/;
if(pos<=mid) update(id*,pos,val);
else update(id*+,pos,val);
pushup(id);
}
int main()
{
int T;
cin>>T;
while(T--)
{
int N,M;
cin>>N>>M;
for(int i=;i<=N;i++) scanf("%d",&elem[i]);
build_tree(,N,);
while(M--)
{
char S[];
int from,to;
scanf("%s%d%d",S,&from,&to);
if(S[]=='Q') printf("%d\n",query(from+,to+,));
else update(,from+,to);
}
}
return ;
}