51nod 1376 最长递增子序列的数量(线段树)-白红宇

51nod 1376 最长递增子序列的数量(线段树)

阅读量：6633 次

发布时间：2019-06-25

本文共 3321 字，大约阅读时间需要 11 分钟。

51nod 1376 最长递增子序列的数量

数组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示例

/*51nod 1376 最长递增子序列的数量problem:给你一个数组,求其中最长递增子序列有多少个solve:对于第i个数a[i]而言,它需要知道已经出现的[1,a[i]-1]中最长递增子序列的长度以及数量. 所以可以利用线段树来维护,然后利用长度和数量来更新a[i]hhh-2016/09/03-16:41:1*/#pragma comment(linker,"/STACK:124000000,124000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfs(a) scanf("%s",a)#define scanfl(a) scanf("%I64d",&a)#define scanfd(a) scanf("%lf",&a)#define key_val ch[ch[root][1]][0]#define eps 1e-7#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const ll mod = 1000000007;const int maxn = 50010;const double PI = acos(-1.0);int a[maxn],t[maxn];struct node{ int l,r; ll Max,num; int mid;} tree[maxn << 2];void push_up(int i){ if(tree[lson].Max == tree[rson].Max) { tree[i].Max = tree[lson].Max; tree[i].num = tree[lson].num + tree[rson].num; tree[i].num %= mod; } else if(tree[lson].Max > tree[rson].Max) { tree[i].Max = tree[lson].Max; tree[i].num = tree[lson].num; } else { tree[i].Max = tree[rson].Max; tree[i].num = tree[rson].num; }}void build(int i,int l,int r){ tree[i].l = l,tree[i].r = r; tree[i].Max = tree[i].num = 0; tree[i].mid = (l+r) >> 1; if(l == r) return ; build(lson,l,tree[i].mid); build(rson,tree[i].mid + 1,r); push_up(i);}void push_down(int i){}void update(int i,int k,ll len,ll many){ if(tree[i].l == tree[i].r && tree[i].l == k) { if(tree[i].Max < len) tree[i].Max = len,tree[i].num = many; else if(tree[i].Max == len) tree[i].num += many; tree[i].num %= mod; return ; } int mid = tree[i].mid; if(k <= mid) update(lson,k,len,many); else update(rson,k,len,many); push_up(i);}ll tans,tnum;void query(int i,int l,int r){ if(l > r) { tans = 0,tnum = 1; return ; } if(tree[i].l >= l && tree[i].r <= r) { if(tans == -1) tans = tree[i].Max,tnum = tree[i].num; else { if(tans == tree[i].Max) tnum += tree[i].num; else if(tans < tree[i].Max) { tans = tree[i].Max,tnum = tree[i].num; } tnum %= mod; } return ; } push_down(i); int mid = tree[i].mid; if(l <= mid) query(lson,l,r); if(r > mid) query(rson,l,r); return;}int cnt = 0;int main(){ int n; while(scanfi(n) != EOF) { for(int i = 0; i< n;i++){ scanfi(a[i]); t[i] = a[i]; } sort(a,a+n); cnt = 0; for(int i = 1;i < n;i++) { if(a[i] != a[cnt]) a[++cnt] = a[i]; }// for(int i = 0;i <= cnt;i++)// printf("%d\n",a[i]); build(1,0,cnt); ll tMax = 0,ans = 0; int id = lower_bound(a,a+cnt+1,t[0]) -a; update(1,id,1,1); tMax = 1,ans = 1; for(int i = 1;i < n;i++) { id = lower_bound(a,a+cnt+1,t[i]) -a;// cout << id <<" " ; tans = -1,tnum = 0; query(1,0,id-1); if(!tans && !tnum) tnum = 1; if(tMax < tans+ 1) tMax = tans+1,ans = tnum; else if(tMax == tans+1) ans += tnum; ans %= mod; update(1,id,tans + 1,tnum); }// cout <

转载于:https://www.cnblogs.com/Przz/p/5837488.html

你可能感兴趣的文章