把数组离散化后,用树状数组维护某个值结尾的符合要求的子序列数量,枚举每一个数组中的数,查询比他大的结尾的子序列个数sum,ans+=sum+1(1是他本身),add(id,sum+1)即可
#include <bits/stdc++.h>
using namespace std;
小红有一个长度为n的数组a1,a2,...,an,请你帮助他求出有多少个严格单调递减的子序列。结果可能很大,对109+7取模后在输出。
严格单调递减序列是指一个序列满足:长度为1或从第2项开始,每一项均小于前一项的序列。
由原来的序列删除(或不删除)某些元素而不改变其余元素的相对顺序的序列称为子序列。
第一行输入一个整数 n(1≤n≤2×105)代表数组中的元素数量。
第二行输入n个整数a1,a2,...,an(1≤ai≤109)代表元素。
在一行输出一个整数,代表严格单调递减的子序列的个数,由于数据较大,输出答案对109+7取模的结果。
输入
4
1 3 5 2
输出
6
说明
由两个元素构成的满足题意的子序列为{3,2}、{5,2}