LYOJ 215 「雅礼集训 2017 Day10」数列

## 题目描述
小 A 有 $N$ 个正整数，紧接着，他打算依次在黑板上写下这 $N$ 个数。对于每一个数，他可以决定将这个数写在当前数列的最左边或最右边。现在他想知道，他写下的数列的可能的最长严格上升子序列（可由不连续的元素组成）的长度是多少，同时他还想知道有多少种不同的最长的严格上升子序列。

两个子序列被认为是不同的，当且仅当：两个子序列属于两个不同的写序列的方案（两个写序列中有至少一步是不一样的）或两个子序列位于同一写序列方案的不同位置。

由于结果可能很大，所以小 A只需要知道最长严格上升子序列的方案数对 $10 ^ 9 + 7$ 取模的结果。
## 输入格式
第一行一个整数 $N$。
第二行 $N$ 个正整数，表示小 A 写下的初始序列。
## 输出格式
输出一行两个整数，最长严格上升子序列的长度以及方案数模 $10 ^ 9 + 7$ 后的结果。
## 样例
### 样例输入 1
2
1 1
### 样例输出 1
1 4
### 样例输入 2
4
2 1 3 4
### 样例输出 2
4 1
## 数据范围与提示
对于 $30\%$ 的数据， $N \leq 20$；
对于 $50\%$ 的数据， $1 \leq N \leq 1000$ 。
对于 $100\%$ 的数据， $1 \leq N \leq 200000$

## 题解

复杂度$O(nlogn)$

因为是严格上升，所以求最长的长度显然可以在开头对称一下后，做一遍LIS就好了。

就像这样

4 3 1 2 2 1 3 4

求得最长的长度之后，我们就只需要统计每个长度为max的子序列可以出现在多少个不同的写法里。显然就是不同的子序列个数$*2^{n-maxlen-1}$次。

```c
#include<bits/stdc++.h>
#define N 200005
const int mod=1e9+7;
using namespace std;
bool cmp(int *a,int *b){return *a<*b;}
int *ls[N],lcnt,buf[N];
void lsh(int sz){
	sort(ls+1,ls+sz+1,cmp);buf[1]=lcnt=1;
	for(int i=2;i<=sz;i++) buf[i]=*ls[i]==*ls[i-1]? buf[i-1]:++lcnt;
	for(int i=1;i<=sz;i++) *ls[i]=buf[i];
}
struct msg{int mx,num;};
msg merge(msg a,msg b){
	if(a.mx==b.mx) return (msg){a.mx,(a.num+b.num)%mod};
	return a.mx<b.mx? b:a;
}
namespace sgt{
	const int L=0,R=1;
	struct xds{
		int son[2],l,r;
		msg x;
	}a[N*2];int cnt;
	void build(int &k,const int &l,const int &r){
		k=++cnt;a[k].x=(msg){0,0};a[k].l=l;a[k].r=r;
		if(l!=r){
			int mid=(l+r)>>1;
			build(a[k].son[L],l,mid);build(a[k].son[R],mid+1,r);
		}
	}
	void add(const int &k,const int &pos,const msg &x){
		if(a[k].l==a[k].r){
			a[k].x=merge(a[k].x,x);
		}else{
			add(a[k].son[ (a[k].l+a[k].r)/2<pos? R:L ],pos,x);
			a[k].x=merge(a[a[k].son[L]].x,a[a[k].son[R]].x);
		}
	}
	msg query(const int &k,const int &pos){
		if(a[k].r<=pos){
			return a[k].x;
		}else{
			int mid=(a[k].l+a[k].r)>>1;
			if(mid<pos) return merge(query(a[k].son[L],pos),query(a[k].son[R],pos));
			else return query(a[k].son[L],pos);
		}
	}
};

int n;
int a[N*2];
int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[n+i]);
	for(int i=1;i<=n;i++) ls[i]=&a[n+i];
	lsh(n);
	for(int i=1;i<=n;i++) a[i]=a[n+n+1-i];
	int root;sgt::build(root,0,n);
	for(int i=1;i<=n*2;i++){
		msg x=sgt::query(root,a[i]-1);
		if(x.mx==0) x=(msg){1,1};
		else x.mx++;
		sgt::add(root,a[i],x);
	}
	msg x=sgt::query(root,n);
	cout<<x.mx<<" ";
	for(int i=1;i<=n-x.mx-1;i++) x.num=x.num*2%mod;
	if(x.mx==n) x.num=1;
	cout<<x.num<<endl;
	return 0;
}
```

wuvin

导航

最近发表

友情链接