51Nod 1376 最长递增子序列的数量(dp+树状数组)

本文主要是介绍51Nod 1376 最长递增子序列的数量(dp+树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

最长递增子序列的题做过不少，让求数量的还是第一次，O(n^2)的代码很好写，但数据范围50000，故无情超时，想了很久，总算有所得。

时间: O(nlog(n)) 空间: O(2*n)

思路
O(n^2)的思路中，每次求以第i个数结尾的最大长度和记录总数都要对前i－1个数进行遍历比较，如果能把这个比较过程转化为对前i项对求和，就可以用树状数组或线段数进行求和优化了。

    重载＋，按照题目需求重新定义求和意义Node operator + (const Node &t) const{if(this->len < t.len)return t;if(this->len > t.len)return (*this);return Node(t.len, (this->cnt + t.cnt) % MOD);

于是有 dp(i) = sum(dp(0, i-1)) + 1;
为什么可以这样呢。我们对序列的数从小到大进行操作，当前数的值等于原有顺序下前面所有数的求和，因为前面比它大的数都还为0尚未更新，不会造成影响，而已更新的数都是比它小的，所以它的值就是前面的求和结果再加1。

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;const int MAX = 50005;
const int MOD = 1000000007;struct Node
{int len, cnt;Node(){}Node(int len, int cnt): len(len), cnt(cnt){}Node operator + (const Node &t) const{if(this->len < t.len)return t;if(this->len > t.len)return (*this);return Node(t.len, (this->cnt + t.cnt) % MOD);}
};struct Num
{int num, pos;
};Node c[MAX];
Num d[MAX];bool cmp(Num &a, Num &b)
{if(a.num == b.num)return a.pos > b.pos;return a.num < b.num;
}void update(Node a,int pos, int n)
{for(int i = pos; i <= n; i += i&(-i))c[i] = c[i] + a;
}Node query(int pos)
{Node ans(0, 0);for(int i = pos-1; i > 0; i -= i&(-i))ans = ans + c[i];return ans;
}int main()
{int n;scanf("%d", &n);for(int i = 0; i < n; ++i){scanf("%d", &d[i].num);d[i].pos = i+1;}sort(d, d+n, cmp);Node ans(0, 0);for(int i = 0; i < n; ++i){Node t = query(d[i].pos);if(++t.len == 1) t.cnt = 1;ans = ans + t;update(t, d[i].pos, n);}printf("%d\n", ans.cnt);return 0;
}