本文主要是介绍hdu(3308)LCIS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定N个数，两种操作U A B：把第A个数变为B（从0开始计数）
Q A B ：查询A到B内，最长的连续上升序列长度
向上更新部分要注意细节
对于左连续的话，可以由左孩子的左连续得来，但是可能包括右孩子的左连续，要进行判断左孩子的左连续是否是整个区间，而且中间的结合是否满足递增
右连续一样。
对于整个区间的最值，可能来源与左右孩子的最值，也可以来源于两个区间的中间部分。
更新部分不需要解释，直接更新到叶子节点，然后通过子节点更新父节点
查询的时候有点麻烦，需要区间合并的时候需要格外注意
左右孩子分别找的结果，以及可能是 两个区间的合并，但是要注意细节
线段树：
B[]保存每个数的值，从1开始计数
节点记录：s，当前区间内最长的连续上升序列长度；ls，左边连续上升的长度；rs，右边连续上升的长度
up(t)，更新当前节点信息。根据左子树、中间、右子树更新，s，ls，rs。注意，当left < right时，才能使用中间。
tree()，如果需要建立子区间，则建立后up(t)
query()，如果需要查询子区间，则需要考虑左、中、右，考虑中间要满足left < right
update()，更新叶子时，需要更新B[]。如果更新子区间后，需要up(t)。
注：left = B[mid], 左区间最右边的值；right = B[mid+1]，右区间最左边的值
#include"string.h"
#include"stdlib.h"
struct point
{
int x,y,sum;
int s,ls,rs;
int len(){return y-x+1;}
}a[400000];
int B[400000];
int min(int a,int b)
{
a=a>b?b:a;
return a;
}
int max(int a,int b)
{
a=a>b?a:b;
return a;
}
void up(int t)
{
int temp=2*t;
a[t].s=max(a[temp].s,a[temp+1].s);
int mid=(a[t].x+a[t].y)/2;
int left=B[mid];
int right=B[mid+1];
if(left<right)
a[t].s=max(a[t].s,a[temp].rs+a[temp+1].ls);
if(a[temp].s==a[temp].len()&&left<right)
a[t].ls=a[temp].s+a[temp+1].ls;
else
a[t].ls=a[temp].ls;
if(a[temp+1].s==a[temp+1].len()&&left<right)
a[t].rs=a[temp+1].s+a[temp].rs;
else
a[t].rs=a[temp+1].rs;
return ;
}
void tree(int t,int x,int y)
{
a[t].x=x;
a[t].y=y;
if(x==y)
{
a[t].s=a[t].ls=a[t].rs=1;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
tree(temp,x,mid);
tree(temp+1,mid+1,y);
up(t);
return ;
}
int query(int t,int x,int y)
{
if(x<=a[t].x&&y>=a[t].y)
{
return a[t].s;
}
int mid=(a[t].x+a[t].y)/2;
int temp=2*t;
if(y<=mid)
return query(temp,x,y);
if(x>mid)
return query(temp+1,x,y);
int left=B[mid];
int right=B[mid+1];
int lm=query(temp,x,mid);
int rm=query(temp+1,mid+1,y);
int mm=0;
if(left<right)
{
mm=min(a[temp].rs,mid-x+1)+min(a[temp+1].ls,y-mid);
}
return max(max(lm,rm),mm);
}
void update(int t,int x,int val)
{
if(a[t].x==a[t].y)
{
B[x]=val;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(x<=mid)
update(temp,x,val);
else
update(temp+1,x,val);
up(t);
return ;
}
int main()
{
int m,n,i,k,h,p;
char str[20];
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&B[i]);
tree(1,1,n);
while(m--)
{
scanf("%s%d%d",str,&h,&p);
if(str[0]=='U')
update(1,h+1,p);
else
{
if(h>p)
{
int T=h;
h=p;
p=T;
}
printf("%d\n",query(1,h+1,p+1));
}
}
}
return 0;
}
这篇关于hdu(3308)LCIS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
