P3970 [TJOI2014]上升子序列
Deu5ExMach1na
·
·
题解
关于此题的一个新的方法：
此题其实不需要其他题解的 last 数组来记录什么的，整体代码长度也比较短。
关键部分的代码：
for (int i = 1; i <= n; i++) {
int val = ask(num[i]) - ask(num[i] - 1);
add(num[i], ask(num[i] - 1));
if (val) add(num[i], -val + 1);
else add(num[i], 1);
}
解释如下：
$add()$，$ask()$ 对应的是树状数组的基操，
对于如何建立树状数组，我们可以这样来考虑：
建立数组 $c[i]$ 保存**当前以 $i$ 结尾的上升子序列的集合的元素个数**。
------------
如何维护 $c[i]$？：
1.遍历 $num[]$。
2.如果当前的数对应的集合为空，则要将 $ c[i] $ 加一，让它变成 $ \{i\}$ 只有一个 $i$ 元素，方便后续转移。
3.遍历到 $i$ 时，我们将它加上 $c[1]$ 到 $c[num[i]-1]$ 的和，这应该是比较好理解的，
但是若 $c[i]$ 本身有值，我们会发现出现了重复，此时把 $c[i]$ 对应集合的元素全重新计算了一遍，所以要**减去 $c[i]$ 原本的值**。
4.注意 $\{i\}$ 没有被重复计算，所以还要 $+1$。
------------
所以答案就是：
`
cout << ask(m) - m;
`
因为 $\{i\}$ 不算做上升序列。
CODE：
```cpp
#include <bits/stdc++。h>
#define int long long
#define mod 1000000000 + 7
#define N 100007
using namespace std;
int n, m;
int num[N], c[N], ls[N];
void add(int x, int v) {
for (; x <= m; x += x & -x) { c[x] += v; c[x] %= mod; }
}
int ask(int x) {
int ret = 0;
for (; x; x -= x & -x) { ret += c[x]; ret %= mod; }
return ret;
}
signed main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> num[i];
ls[i] = num[i];
}
sort(ls + 1, ls + n + 1);
m = unique(ls + 1, ls + n + 1) - (ls + 1);
for (int i = 1; i <= n; i++)
num[i] = lower_bound(ls + 1, ls + 1 + m, num[i]) - ls;
for (int i = 1; i <= n; i++) {
int val = ask(num[i]) - ask(num[i] - 1);
add(num[i], ask(num[i] - 1));
if (val) add(num[i], -val + 1);
else add(num[i], 1);
}
cout << ask(m) - m;
return 0;
}
```