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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 #define eps 1e-7 #define pll pair 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); } vectorv; 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; } }