NOI模拟赛(3.15) sequence(序列)

Description

小A有N个正整数，紧接着，他打算依次在黑板上写下这N个数。对于每一个数，他可以决定将这个数写在当前数列的最左边或最右边。现在他想知道，他写下的数列的可能的最长严格上升子序列（可由不连续的元素组成）的长度是多少，同时他还想知道有多少种不同的最长的严格上升子序列。
两个子序列被认为是不同的当且仅当：两个子序列属于两个不同的写序列方案（两个写序列方案中有至少一步是不一样的）或两个子序列位于同一写序列方案的不同位置。
由于结果可能很大，所以小A只需要知道最长严格上升子序列的方案数对10^9+7取模的结果。

Input

第一行一个正整数N（1<=N<=2*10^5）。
第二行包含N个由空格隔开的正整数，表示小A写下的初始序列。序列中的每一个元素小于等于10^9。

Output

输出包含一行，输出最长严格上升子序列的长度以及方案数对10^9+7取模的结果。

Sample Input

Sample Output

输出1：

1 4

输出2：

4 1

Data Constraint

30%的数据满足：N<=20
50%的数据满足：N<=1000

Solution

题目有一个隐藏性质是这样的

答案的第一问是对于每个点为结束点或开始点求出的最长上升序列长度和最长下降序列长度之和

在dp以上两个值的过程中同时统计方案数，用树状数组可以n log n时间复杂度做到

#include <vector>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define set_file(File) freopen(#File".in", "r", stdin), freopen(#File".out", "w", stdout)

#define close_file() fclose(stdin), fclose(stdout)

#define ll long long

#define mo 1000000007

#define maxn 200010

template<class T> inline void Rin(T &x)

	{

	int c = getchar();

	for(x = 0; c < 48 || c > 57; c = getchar());

	for(; c > 47 && c < 58; c = getchar()) x = (x << 1) + (x << 3) + c - 48;

	}

std::vector<int> VeH;

int n, seq[maxn], mx[maxn], c[maxn], f[maxn], fs[maxn], g[maxn], gs[maxn];

void get_ans_lef(int i)

	{

	int x = seq[i] - 1, tot = 1, ans = 0;

	for(; x; x -= x & -x)

		{

		if(mx[x] > ans) ans = mx[x], tot = c[x];

		else if(mx[x] == ans) tot = (tot + c[x]) % mo;

		}

	f[i] = ans + 1, fs[i] = tot;

	x = seq[i];

	for(; x <= n; x += x & -x)

		{

		if(mx[x] < f[i]) mx[x] = f[i], c[x] = fs[i];

		else if(mx[x] == f[i]) c[x] = (c[x] + fs[i]) % mo;

		}

	}

void get_ans_rig(int i)

	{

	int x = seq[i] - 1, tot = 1, ans = 0;

	for(; x; x -= x & -x)

		{

		if(mx[x] > ans) ans = mx[x], tot = c[x];

		else if(mx[x] == ans) tot = (tot + c[x]) % mo;

		}

	g[i] = ans + 1, gs[i] = tot;

	x = seq[i];

	for(; x <= n; x += x & -x)

		{

		if(mx[x] < g[i]) mx[x] = g[i], c[x] = gs[i];

		else if(mx[x] == g[i]) c[x] = (c[x] + gs[i]) % mo;

		}

	}

int main()

	{

	set_file(sequence);

	Rin(n);

	for(int i = n; i; i--)

		{

		Rin(seq[i]);

		VeH.push_back(seq[i]);

		}

	std::sort(VeH.begin(), VeH.end());

	VeH.erase(unique(VeH.begin(), VeH.end()), VeH.end());

	for(int i = 1; i <= n; i++) seq[i] = std::lower_bound(VeH.begin(), VeH.end(), seq[i]) - VeH.begin() + 1;

	for(int i = 1; i <= n; i++) get_ans_lef(i);

	memset(mx, 0, sizeof mx);

	memset(c, 0, sizeof c);

	for(int i = 1; i <= n; i++) seq[i] = n - seq[i] + 1;

	for(int i = 1; i <= n; i++) get_ans_rig(i);

	int tot = 0, ans = 0;

	for(int i = 1; i <= n; i++)

		if(f[i] + g[i] - 1 > ans) ans = f[i] + g[i] - 1, tot = (ll)fs[i] * gs[i] % mo;

		else if(f[i] + g[i] - 1 == ans) tot = (tot + (ll)fs[i] * gs[i] % mo) % mo;

	for(int i = 1; i <= n - ans; i++) tot = (ll)tot * 2 % mo;

	printf("%d %d\n", ans, tot);

	close_file();

	return 0;

	}

秒客网