自动搬运

查看原文

来自洛谷，原作者为

	Deu5ExMach1na ""

搬运于2025-08-24 21:55:04，当前版本为作者最后更新于2021-11-26 11:36:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于此题的一个新的方法：

此题其实不需要其他题解的 $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);
  }

解释如下：

$num[i]$ 储存的是原来序列的数，

$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：

#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;
}