51Nod 1376 最长递增子序列的数量 —— LIS、线段树

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1376

基准时间限制：1 秒空间限制：131072 KB 分值: 160 难度：6级算法题

关注

数组A包含N个整数（可能包含相同的值）。设S为A的子序列且S中的元素是递增的，则S为A的递增子序列。如果S的长度是所有递增子序列中最长的，则称S为A的最长递增子序列（LIS）。A的LIS可能有很多个。例如A为：{1 3 2 0 4}，1 3 4，1 2 4均为A的LIS。给出数组A，求A的LIS有多少个。由于数量很大，输出Mod 1000000007的结果即可。相同的数字在不同的位置，算作不同的，例如 {1 1 2} 答案为2。

Input

第1行：1个数N，表示数组的长度。(1 <= N <= 50000)

第2 - N + 1行：每行1个数A[i]，表示数组的元素(0 <= A[i] <= 10^9)

Output

输出最长递增子序列的数量Mod 1000000007。

Input示例

Output示例

题解：

1.由于要统计个数，所以就不能用之前所谓的O(n^2)或O(nlogn)方法（这两种方法求的是LIS的长度，而不是个数）。

2.因此需要利用线段树进行统计：将输入的值进行离散化，然后在离散化后数组之上建立线段树（即以值建树而不是以下标建树）。线段树的每个结点需要记录两个信息：该段的LIS的长度及个数。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 5e4+;

 pair<int,int> getMax(pair<int,int> x, pair<int,int>y)

 {

     if(x.first<y.first) x = y;

     else if(x.first==y.first) x.second = (x.second+y.second)%MOD;

     return x;

 }

 pair<int,int> len[MAXN*];

 void build(int u, int l, int r)

 {

     if(l==r)

     {

         len[u].first = len[u].second = ;

         return;

     }

     int mid = (l+r)>>;

     build(u*,l,mid);

     build(u*+,mid+,r);

     len[u] = getMax(len[u*],len[u*+]);

 }

 void add(int u, int l, int r, int pos, pair<int,int> val)

 {

     if(l==r)

     {

         len[u] = getMax(len[u],val);

         return;

     }

     int mid = (l+r)>>;

     if(pos<=mid) add(u*,l,mid,pos,val);

     else add(u*+,mid+,r,pos,val);

     len[u] = getMax(len[u*],len[u*+]);

 }

 pair<int,int> query(int u, int l, int r, int x, int y)

 {

     if(x<=l&&r<=y) return len[u];

     int mid = (l+r)>>;

     pair<int,int> ret = make_pair(,);

     if(x<=mid) ret = getMax(ret,query(u*,l,mid,x,y));

     if(y>=mid+) ret = getMax(ret,query(u*+,mid+,r,x,y));

     return ret;

 }

 int a[MAXN], M[MAXN], m;

 int main()

 {

     int n;

     while(scanf("%d",&n)!=EOF)

     {

         for(int i = ; i<=n; i++)

             scanf("%d",&a[i]);

         memcpy(M+,a+,n*sizeof(a[]));

         M[n+] = -INF;  //在最前面加个无穷小，防止区间溢出

         sort(M+,M++n+);         //离散化

         m = unique(M+,M++n+)-(M+);

         build(,,m);

         for(int i = ; i<=n; i++)

         {

             int pos = lower_bound(M+,M++m,a[i])-(M+);    //找到a[i]的上一个值的位置（这也是为什么要在离散化数组里加个无穷小）

             pair<int,int> t = query(,,m,,pos);

             if(t.first==) t.first = t.second = ;  //如果在前面没人比它小，则自己作为第一个

             else t.first++;     //如果前面有人比它小，则长度+1（加上自己）

             add(,,m,pos+,t);     //插入

         }

         printf("%d\n", query(,,m,,m).second);

     }

 }

秒客网

51Nod 1376 最长递增子序列的数量 —— LIS、线段树

相关文章