题意
个正整数按顺序依次加入到数列里，可以决定将这个数写在当前数列的最左边或最右边。写下的数列的可能的最长严格上升子序列的长度是多少，搞出这样的子序列有多少种。加入数列的方法或子序列下标不同则认为两子序列不同。
此题还出现在：「雅礼集训 2017 Day10」数列。
思路
我们考虑取出 LIS 中那个最先被加入到数列中的位置（称其为 首位置），将 LIS 断开成左右两个部分。根据加入数列的方式，这个位置的原始下标是最小的。从此位置开始，前面的越往左，原始下标越大，数值越小；后面的越往右，原始下标越大，数值越大。
根据此发现，得出前面的部分以严格下降子序列的形式出现在原数组中；后面的部分以严格上升子序列的形式出现在原数组中。
对于原数组中的每一个位置 ，我们钦定其为最终 LIS 的 首位置，其原始下标是 LIS 中最小的。那么其余的 LIS 中的元素的原始下标都大于 ，于是结合之前的推论，我们只需要找到 中的最长严格上升和下降子序列然后合并即可。因为两个都是严格上升下降的，所以没有交集，可以独立地求。
后缀 LIS 考虑倒着一位位地算 LIS，树状数组优化 dp 的求法不必赘述了吧。在维护最大值的过程中，同时维护数量，即遇到更大的则覆盖，遇到相同的就把数量加上去。
最终对于每个位置 ，设最长上升子序列长度为 ，方案数为 ；最长下降子序列长度为 ，方案数为 。则总长度数是 ，方案数是 。
对于未被选入 LIS 的 个位置，只要插进去了就行，从前面插还是从后面插无所谓，有 种插法。总答案为 。
时间复杂度：。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5, mod = 1e9 + 7;
ll n, a[N], mx, ct;
struct node {
ll val = 0, cnt = 0;
};
node fu[N], fd[N];
ll tot;
set<ll> s;
unordered_map<ll, ll> mp;
void D() {
for (ll i = 1; i <= n; i++) {
cin >> a[i];
s.insert(a[i]);
}
for (ll o : s) {
mp[o] = ++tot;
}
for (ll i = 1; i <= n; i++) {
a[i] = mp[a[i]];
}
}
ll to(ll x) {
return n + 1 - x;
}
ll qpow(ll x, ll y) {
if (y == 0) {
return 1;
}
ll res = qpow(x, y / 2);
res = res * res % mod;
if (y % 2) {
res = res * x % mod;
}
return res;
}
struct bit {
node tr[N];
node merge(node x, node y) {
if (x.val == y.val) {
return { x.val, (x.cnt + y.cnt) % mod };
} else if (x.val > y.val) {
return x;
} else {
return y;
}
}
void update(ll x, node k) {
for (; x < N; x += x & -x) {
tr[x] = merge(tr[x], k);
}
}
node query(ll x) {
node res = { 0, 1 };
for (; x; x -= x & -x) {
res = merge(res, tr[x]);
}
return res;
}
} tu, td;
void solve() {
cin >> n;
D();
for (ll i = n; i >= 1; i--) {
fd[i] = td.query(a[i] - 1), fd[i].val++, td.update(a[i], fd[i]);
fu[i] = tu.query(to(a[i] + 1)), fu[i].val++, tu.update(to(a[i]), fu[i]);
}
for (ll i = 1; i <= n; i++) {
ll len = fd[i].val + fu[i].val - 1;
if (len > mx) {
mx = len, ct = fd[i].cnt * fu[i].cnt % mod;
} else if (len == mx) {
(ct += fd[i].cnt * fu[i].cnt % mod) %= mod;
}
}
cout << mx << " " << ct *qpow(2, n - mx) % mod << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
暂无评论