Description 给你一个正整数序列,问其中有多少个严格上升子序列?答案模上1e9+7 Input 第一行为T代表有多少组数据.T≤10 每组数据以N开始,代表有多少个数.N≤105 接下来一行包括N个数字a1,a
Description
给你一个正整数序列,问其中有多少个严格上升子序列?答案模上1e9+7
Input
第一行为T代表有多少组数据.T≤10
每组数据以N开始,代表有多少个数.N≤105
接下来一行包括N个数字a1,a2,…an.
在
范
围
内
ai在int范围内
Output
每组样例输出一行。
Sample Input
3
3
1 1 2
5
1 2 1000 1000 1001
3
1 10 11
Sample Output
5
23
7
询问一个序列有多少个严格上升子序列；
思路：考虑以某个数为结尾的贡献，那么这个贡献应该是在它前面比它小的数的贡献之和，那么我们就要计算前缀和，用树状数组维护
不错的一道题；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 300005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
vector<ll>v;
int a[maxn];
int tmp[maxn];
int n;
void add(int x, int val) {
for (x; x <= n; x+=(x&-x)) {
tmp[x] += val;
tmp[x] %= mod;
}
}
ll sumt(int x) {
ll ans = 0;
for (x; x;) {
ans += tmp[x];
ans %= mod;
x = x - (x&-x);
}
return ans;
}
int toid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
cin >> n;
int i, j;
v.clear();
memset(a, 0, sizeof(a));
memset(tmp, 0, sizeof(tmp));
for (i = 1; i <= n; i++) {
cin >> a[i];
v.push_back(a[i]);
}
sort(v.begin(), v.end());
ll ans = 0;
v.erase(unique(v.begin(), v.end()), v.end());
int loct;
for (i = 1; i <= n; i++) {
loct = toid(a[i]);
ll tp = sumt(loct - 1) + 1;
add(loct, tp);
ans = (ans + tp) % mod;
}
cout << ans << endl;
}
}