# 题目大意
就是找不下降子序列的个数。
# 解题思路
一开始想着先离散化，然后再做个 $dp$，发现用 $dp$ 的话时间复杂度是 $\text{O}(n^2)$ 的，稳稳超时。
这里说说 $dp$:
设 $dp[i]$ 表示以 $a[i]$ 为结尾的不下降子序列的个数。
那么状态转移方程就显而易见了：
$$dp[i] = sum(dp[j])+1,a[j]<=a[i]\&\&j<i$$
遂放弃 $dp$，转向另一种思路：树状数组。
因为要求逆序列的个数。所以选择用树状数组来做，思路如下：
将数据离散化后，按照原来输入的顺序从小到大将每一个数的影响加到树状数组中。那么影响是啥？
就是会对当前这个数后面的比它大的数字造成影响，因为会构成逆序列。然后你就牛逼了。。。
这样的话，每次询问一个数时，只有它前面的数的影响才被加了进去。就可以保证询问的正确性。
# 附上代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e5+
3, HA = 1e9+
7;
int n, s[maxn], a[maxn], tmp[maxn], bit[maxn], NI[maxn];
inline int lowbit(
int x) {
return x & -
x;}
inline void add(
int pos,
int num) {
while (pos <=
n) {
bit[pos] = ((num % HA) + (bit[pos] % HA)) %
HA;
pos +=
lowbit(pos);
}
}
inline int query(
int pos) {
int res =
0;
while (pos >=
1) {
res = ((bit[pos] % HA) + (res % HA)) %
HA;
pos -=
lowbit(pos);
}
return res;
}
int main() {
while (~scanf(
"%d", &
n)) {
memset(NI, 0,
sizeof(NI));
memset(bit, 0,
sizeof(bit));
for(
int i=
1; i<=n; i++
) {
scanf("%d", &
s[i]);
tmp[i] =
s[i];
}
sort(tmp+
1, tmp+
1+
n);
for(
int i=
1; i<=n; i++
)
a[i] = lower_bound(tmp+
1, tmp+
1+n, s[i])-
tmp;
for(
int i=
1; i<=n; i++
) {
NI[i] =
query(a[i]);
NI[i] %=
HA;
add(a[i], NI[i] +
1);
}
printf("%d\n", query(n));
}
}
转载于:https://www.cnblogs.com/bljfy/p/9718708.html
