题目内容

小塔有一个长度为$n$的数组$a_1,a_2,...,a_n$，请你帮助他求出有多少个严格单调递减的子序列。结果可能很大，对$10^9+7$取模后在输出。

严格单调递减序列是指一个序列满足：长度为$1$或从第$2$项开始，每一项均小于前一项的序列。

由原来的序列删除(或不删除)某些元素而不改变其余元素的相对顺序的序列称为子序列。

输入描述

第一行输入一个整数 $n$($1≤n≤2×10^5$)代表数组中的元素数量。

第二行输入n个整数$a_1,a_2,...,a_n$($1≤a_i≤10^9$)代表元素。

输出描述

在一行输出一个整数，代表严格单调递减的子序列的个数，由于数据较大，输出答案对$10^9+7$取模的结果。

样例1

输入

4
1 3 5 2

输出

6

说明

由两个元素构成的满足题意的子序列为{$3,2$}、{$5,2$}

【入门题】暴力拿分法1

• IOI赛制

IOI赛制介绍

我们目前的碰到几乎所有大厂笔试，所使用的都是IOI赛制。通俗来讲，该赛制允许进行无数次提交，按最高分计算。每次提交后台有n组测试样例(一组样例由一个输入数据和一个输出数据组成)，我们所得的分数为$\frac{正确的组数}{n}*100\%$。也就是说我们允许使用非标准解法拿部分分

IOI赛制中的常见技巧-暴力拿(骗)分法

一种最常见的技巧是：碰到想不出满分最优解的题目，我们可以迅速的用暴力写完拿完部分分(部分情况下可达70%)，把时间留给我们会的题目。我们本道题目是来自24年字节跳动9.25机考最后一道题目，是一道较困难的，数据结构优化的动态规划题目。

正确思路

是需要使用线段树或者树状数组维护某个值结尾的符合要求的子序列数量，进行区间查询和单点修改的，并且要加上取模运算+离散化。把复杂度降到o(nlogn),才能拿到全部分数。首先所需的知识点非常的多且是笔试中能碰到最难的知识点。(感兴趣可以划到本篇题解的最下面)

出题人往往会在数据范围上手软(毕竟是求职考试，不是竞赛考试，出题人往往会倾向于宽容而不是苛刻)，所以我们可以考虑拿到部分分数(根据考生反馈，该做法在考场上能拿到50%+的通过率，但聊胜于无！)，如果时间足够在考虑进行满分思路。

题面描述

小塔有一个长度为 n 的数组 a[1], a[2], ..., a[n]。需要计算数组中严格单调递减的子序列的个数。严格单调递减的子序列指的是长度为1的序列，或者从第二项开始，每一项都小于前一项的序列。由于结果可能非常大，最终需要对 (10^9 + 7) 取模输出。

骗分思路

采用暴力的双重循环方法遍历数组，统计所有严格单调递减的子序列。具体步骤如下：

1. 初始化一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的严格单调递减子序列的个数。初始时，每个元素本身可以作为一个长度为1的子序列，因此 dp[i] = 1。
2. 使用两重循环，外层循环遍历数组的每一个元素 i，内层循环遍历 i 之前的所有元素 j。
3. 对于每一对 (j, i)，如果 a[j] > a[i]，则可以将以 a[j] 结尾的所有子序列在其后追加 a[i]，从而形成新的严格单调递减子序列。因此，将 dp[j] 的值加到 dp[i] 上。
4. 最后，将所有 dp[i] 的值相加，即为所有严格单调递减子序列的总数。
5. 由于结果可能很大，所有的计算都在取模 (10^9 + 7) 的范围内进行。

代码步骤与对应代码

1. 读取输入并初始化变量

   int n;
   cin >> n;
   vector<long long> a(n);
   for(int i = 0; i < n; ++i){
       cin >> a[i];
   }
   const int MOD = 1e9 + 7;
   

2. 初始化 dp 数组，每个位置初始为1

   vector<long long> dp(n, 1);
   

3. 双重循环计算 dp 数组

   for(int i = 1; i < n; ++i){
       for(int j = 0; j < i; ++j){
           if(a[j] > a[i]){
               dp[i] = (dp[i] + dp[j]) % MOD;
           }
       }
   }
   

4. 计算所有 dp[i] 的总和并输出

   long long result = 0;
   for(int i = 0; i < n; ++i){
       result = (result + dp[i]) % MOD;
   }
   cout << result;
   

完整代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    const int MOD = 1e9 + 7;
    // dp[i]表示以a[i]结尾的严格单调递减子序列的个数
    vector<long long> dp(n, 1); // 每个元素本身可以作为一个子序列
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j){
            if(a[j] > a[i]){
                dp[i] = (dp[i] + dp[j]) % MOD;
            }
        }
    }
    long long result = 0;
    for(int i = 0; i < n; ++i){
        result = (result + dp[i]) % MOD;
    }
    cout << result;
    return 0;
}

以下是满分做法，但不是我们这门课的重点，您不用死磕该解法

满分做法：树状数组（Fenwick Tree）+ 离散化

1. 离散化：

   • 数组中的元素范围可能很大（最高可达 (10^9)），为了能够在树状数组中高效地进行查询和更新，需要将数组元素进行离散化处理。离散化的过程包括：
     • 收集数组中的所有元素。
     • 对这些元素进行排序并去重，得到一个有序且不重复的数组 alls。
     • 将原数组中的每个元素替换为其在 alls 中的排名（1-based）。

2. 树状数组的应用：

   • 树状数组用于维护以某个值结尾的严格单调递减子序列的数量。
   • 遍历数组中的每个元素 a[i]，对于当前元素 a[i]：
     • 查询树状数组中所有大于 a[i] 的元素对应的子序列数量之和 sum。
     • 当前元素 a[i] 本身也可以作为一个长度为1的子序列，因此当前元素贡献的子序列数量为 sum + 1。
     • 将 sum + 1 更新到树状数组中对应 a[i] 的位置。
     • 将 sum + 1 累加到最终答案中。
   • 由于我们需要查询大于 a[i] 的元素，而离散化后的 alls 是升序排列，我们可以通过调整查询方式来实现。

3. 取模运算：

   • 由于结果可能非常大，需要在每一步操作后对结果进行取模 (10^9 + 7)。

具体步骤

1. 输入读取与离散化：

   • 读取数组长度 n 和数组元素。
   • 将所有元素收集到 alls 数组中。
   • 对 alls 进行排序并去重。
   • 使用二分查找将原数组中的元素替换为其在 alls 中的排名。

2. 树状数组初始化与操作：

   • 初始化树状数组 BIT，其大小为离散化后唯一元素的个数。
   • 定义 add 操作用于更新树状数组。
   • 定义 query 操作用于查询树状数组中的前缀和。

3. 遍历数组并计算答案：

   • 遍历数组中的每个元素 a[i]：
     • 查找 a[i] 在离散化数组中的排名 id。
     • 查询树状数组中所有排名大于 id 的子序列数量之和 sum。
     • 当前元素贡献的子序列数量为 sum + 1。
     • 将 sum + 1 更新到树状数组中对应 id 的位置。
     • 将 sum + 1 累加到最终答案中。

4. 输出结果：

   • 最终输出累加得到的答案，对 (10^9 + 7) 取模。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 常量定义
const int MOD = 1e9 + 7;

// 树状数组（Fenwick Tree）结构
struct BIT {
    int size;
    vector<ll> tree;

    BIT(int n) : size(n), tree(n + 1, 0) {}

    // 在索引x处增加value
    void add(int x, ll value) {
        while (x <= size) {
            tree[x] = (tree[x] + value) % MOD;
            x += x & -x;
        }
    }

    // 查询前缀和 [1, x]
    ll query(int x) const {
        ll res = 0;
        while (x > 0) {
            res = (res + tree[x]) % MOD;
            x -= x & -x;
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> alls;
    alls.reserve(n);

    // 读取数组并收集所有元素用于离散化
    for(int &x : a){
        cin >> x;
        alls.push_back(x);
    }

    // 离散化：排序并去重
    sort(alls.begin(), alls.end(), greater<int>()); // 降序排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 树状数组的大小为离散化后的唯一元素个数
    int size = alls.size();
    BIT bit(size);

    ll ans = 0;

    // 遍历数组中的每个元素
    for(int i = 0; i < n; ++i){
        // 在降序排序的alls中找到a[i]的索引（1-based）
        int id = lower_bound(alls.begin(), alls.end(), a[i], greater<int>()) - alls.begin() + 1;

        // 查询比a[i]大的所有元素对应的子序列数之和
        ll sum = bit.query(id - 1); // 因为alls是降序，所以id-1之前的元素都大于a[i]

        // 当前元素自身也可以作为一个子序列
        ll res = (sum + 1) % MOD;

        // 累加到答案中
        ans = (ans + res) % MOD;

        // 更新树状数组
        bit.add(id, res);
    }

    cout << ans;
    return 0;
}