fork(1) download
  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
stdin
Standard input is empty
stdout
1