题目内容

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

树状数组+离散化

把数组离散化后，用树状数组维护某个值结尾的符合要求的子序列数量，枚举每一个数组中的数，查询比他大的结尾的子序列个数sum,ans+=sum+1(1是他本身),add(id,sum+1)即可

代码如下

cpp

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