【HDU3308】LCIS

题目大意：维护一个长度为 N 的序列，支持单点修改，区间查询最长连续上升子序列的长度。

题解：

线段树维护一段区间左端点开始的 LCIS 长度，右端点开始的 LCIS 长度以及区间最优解。考虑进行合并，合并后区间的最优解可能由三部分构成，即：左区间的最优解、右区间的最优解和左区间rmx+右区间lmx的值。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

int n,m,a[maxn];

struct node{

	#define ls(o) t[o].lc

	#define rs(o) t[o].rc

	int lc,rc,lmx,rmx,mx;

}t[maxn<<1];

int tot,root;

inline void pushup(int o,int l,int r){

	int mid=l+r>>1;

	t[o].mx=max(max(t[ls(o)].mx,t[rs(o)].mx),a[mid]<a[mid+1]?t[ls(o)].rmx+t[rs(o)].lmx:0);

	t[o].lmx=t[ls(o)].lmx==mid-l+1&&a[mid]<a[mid+1]?t[ls(o)].lmx+t[rs(o)].lmx:t[ls(o)].lmx;

	t[o].rmx=t[rs(o)].rmx==r-mid&&a[mid]<a[mid+1]?t[rs(o)].rmx+t[ls(o)].rmx:t[rs(o)].rmx;

}

int build(int l,int r){

	int o=++tot;

	if(l==r){t[o].lmx=t[o].rmx=t[o].mx=1;return o;}

	int mid=l+r>>1;

	ls(o)=build(l,mid),rs(o)=build(mid+1,r);

	pushup(o,l,r);

	return o;

}

void modify(int o,int l,int r,int pos){

	if(l==r)return;

	int mid=l+r>>1;

	if(pos<=mid)modify(ls(o),l,mid,pos);

	else modify(rs(o),mid+1,r,pos);

	pushup(o,l,r);

}

int query(int o,int l,int r,int x,int y){

	if(l==x&&r==y)return t[o].mx;

	int mid=l+r>>1;

	if(y<=mid)return query(ls(o),l,mid,x,y);

	else if(x>mid)return query(rs(o),mid+1,r,x,y);

	else{

		int ansl=query(ls(o),l,mid,x,mid);

		int ansr=query(rs(o),mid+1,r,mid+1,y);

		int ret=0;

		if(a[mid]<a[mid+1])ret=min(t[ls(o)].rmx,mid-x+1)+min(t[rs(o)].lmx,y-mid);

		return max(ret,max(ansl,ansr));

	}

}

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	root=build(1,n);

}

void solve(){

	char opt[2];

	int x,y;

	while(m--){

		scanf("%s%d%d",opt,&x,&y);

		if(opt[0]=='Q')++x,++y,printf("%d\n",query(root,1,n,x,y));

		else ++x,a[x]=y,modify(root,1,n,x);

	}

}

void init(){memset(t,0,sizeof(t)),tot=0;}

int main(){

	int T;scanf("%d",&T);

	while(T--){

		init();

		read_and_parse();

		solve();

	}

	return 0;

}

巴特西

【HDU3308】LCIS

最新文章

热门文章