fork(9) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. const long N = 100000 + 10;
  4. const long MOD = 1000000007;
  5. using namespace std;
  6. typedef long long LL;
  7. int res = 0;
  8. int n, a[N], b[N], t[4*N], cf[4*N], f[N], cs[N],ca[N], id = 0;
  9. bool cmp(int i,int j)
  10. {
  11.     return a[i] < a[j];
  12. }
  13. void discretization() //roi rac
  14. {
  15.     for (int i = 1; i <= n; i++) b[i] = a[i], cs[i] = i;
  16.     sort(cs+1,cs+n+1,cmp);
  17.     sort(b+1,b+n+1);
  18.     int it = 0;
  19.     for (int i = 1; i <= n; i++) {
  20.         if ( b[i] != b[i-1] ) a[cs[i]] = ++it;
  21.         else a[cs[i]] = it;
  22.     }
  23.     for (int  i = 1; i <= n; i++)  b[i] = 0;
  24. }
  25. void update(int k,int l,int r,int u,int v,int cc)
  26. {
  27.     if ( l > v || r < u ) return;
  28.     if ( l >= u && r <= v ) {
  29.         if ( cc == 0 ) {
  30.         f[k] = cc;
  31.         t[k] = cc;
  32.         } else f[k] = (f[k] + cc) % MOD;
  33.         return;
  34.     }
  35.     if ( t[k] != -1 ) {
  36.         f[2*k] = t[k];
  37.         t[2*k] = t[k];
  38.         t[2*k+1] = t[k];
  39.         f[2*k+1] = t[k];
  40.         t[k] = -1;
  41.     }
  42.     int mid;
  43.     mid = (l+r)/2;
  44.     update(k*2,l,mid,u,v,cc);
  45.     update(k*2+1,mid+1,r,u,v,cc);
  46.     f[k] = (f[k*2] + f[k*2+1]) % MOD;
  47. }
  48. void visit(int k,int l,int r,int u,int v)
  49. {
  50.     if ( l > v || r < u ) return;
  51.     if ( l >= u && r <= v ) {
  52.         res = (res + f[k]) % MOD;
  53.         return;
  54.     }
  55.     if ( t[k] != -1 ) {
  56.         f[2*k] = t[k];
  57.         t[2*k] = t[k];
  58.         t[2*k+1] = t[k];
  59.         f[2*k+1] = t[k];
  60.         t[k] = -1;
  61.     }
  62.     int mid;
  63.     mid = (l+r)/2;
  64.     visit(k*2,l,mid,u,v);
  65.     visit(k*2+1,mid+1,r,u,v);
  66.     f[k] = (f[k*2] + f[k*2+1]) % MOD;
  67. }
  68. int binarysearch(int x)
  69. {
  70.     int l = 0, r = id, m, ans;
  71.     while ( l <= r ) {
  72.         m = (l+r) / 2;
  73.         if ( b[m] < x ) {
  74.             ans = m;
  75.             l = m+1;
  76.         }
  77.         else r = m - 1;
  78.     }
  79.     return ans;
  80. }
  81. int main()
  82. {
  83.     //freopen("NTSEQ.inp","r",stdin);
  84.     //freopen("NTSEQ.out","w",stdout);
  85.     cin >> n;
  86.     for (int i = 1; i <= n; i++) cin >> a[i];
  87.     discretization();
  88.     a[n+1] = N - 5;
  89.     for (int i = 1; i <= 4*n; i++) t[i] = -1;
  90.     for (int i = 1; i <= n+1; i++) { //mang f là mảng đếm phân phối của b[i]; f[b[x]] đến f[b[x+1]-1] quản lý số lượng dãy con có độ dài là x.
  91.         int x;
  92.         b[id+1] = N - 5;
  93.         x =binarysearch(a[i]);	
  94.             if ( ca[a[i]] < x ) update(1,1,n,a[i],a[i],0);	// nếu xuất hiện a[j] = a[i] Ở trước đó mà độ dài tại a[j] < độ dài tại a[i] thì gán f[a[i]] = 0; để k phải cộng nhiều lần.
  95.             if ( a[i] + 1 <= b[x+1]-1)
  96.             update(1,1,n,a[i]+1,b[x+1]-1,0); //gán giá trị tại a[i]+1 đến b[x+1] - 1 = 0; 
  97.  
  98.             b[x+1] = a[i];
  99.             res = 0;
  100.             if ( x == 0 )   res = 1;
  101.             else  visit(1,1,n,b[x],a[i]-1); 
  102.             cf[i] = res; // cf là số dãy con lớn nhất kết thúc = a[i];
  103.             update(1,1,n,a[i],a[i],cf[i]);
  104.  
  105.         if ( x == id ) ++id;
  106.         ca[a[i]] = x; // mang ca[i] là độ dài lớn nhất của dãy tăng dần mà kết thúc ở i; 
  107.     }
  108.     cout << cf[n+1];
  109. }
  110.  
Success #stdin #stdout 0s 7812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/9aKSW1
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!