fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 1e6 + 5; 
  11. const int MOD = 1e9 + 7;  
  12.  
  13. int n; 
  14. int a[N];
  15. int k[N]; 
  16.  
  17. int add(int a, int b) {
  18.     return (a + b) % MOD; 
  19. }
  20.  
  21. // Segment Tree tối ưu precompute
  22.  
  23. int seg[4 * N]; 
  24.  
  25. void update(int id, int l, int r, int pos, int val) {
  26.     if (l > pos || r < pos) return;  
  27.  
  28.     if (l == r) {
  29.         seg[id] += val;  
  30.         return; 
  31.     }
  32.  
  33.     int mid = (l + r) >> 1; 
  34.     update(id * 2, l, mid, pos, val); 
  35.     update(id * 2 + 1, mid + 1, r, pos, val); 
  36.  
  37.     seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  38. }
  39.  
  40. int get(int id, int l, int r, int u, int v) {
  41.     if (l > v || r < u) return 0;  
  42.  
  43.     if (u <= l && r <= v) return seg[id]; 
  44.  
  45.     int mid = (l + r) >> 1; 
  46.  
  47.     return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  48. }
  49.  
  50. // Tìm i đầu tiên sao cho sum[1..i] >= k
  51. int findKth(int id, int l, int r, int k) {
  52.     if (seg[id] < k) return n + 1;  
  53.  
  54.     if (l == r) return l;  
  55.  
  56.     int mid = (l + r) >> 1;  
  57.  
  58.     int ans_child_l = findKth(id * 2, l, mid, k); 
  59.     if (ans_child_l <= n) return ans_child_l; 
  60.  
  61.     return findKth(id * 2 + 1, mid + 1, r, k - seg[id * 2]); 
  62. }
  63.  
  64. int nxt[N]; // nxt[l] là vị trí l' đầu tiên > l sao cho a[l'] == a[l]  
  65. int first_r[N]; // first_r[l]: đầu mút r đầu tiên thoả mãn đoạn [l, r] có >= k[l] giá trị phân biệt
  66.  
  67. void precompute() {
  68.     map<int, int> last;  
  69.  
  70.     for (int l = n; l >= 1; l--) {
  71.         nxt[l] = last.count(a[l]) ? last[a[l]] : n + 1;  
  72.         last[a[l]] = l;  
  73.     }
  74.  
  75.     for (int l = n; l >= 1; l--) {
  76.         if (nxt[l] <= n) update(1, 1, n, nxt[l], -1); 
  77.         update(1, 1, n, l, 1); 
  78.         first_r[l] = findKth(1, 1, n, k[l]); 
  79.     }
  80. }
  81.  
  82. int dp[N]; // dp[l] = có bao nhiêu cách phân rã đoạn [l, n] 
  83. int suf_dp[N]; // suf_dp[l] = tổng các dp[] trong đoạn [l, n] 
  84.  
  85. int main() {
  86.     ios::sync_with_stdio(0); cin.tie(0);    
  87.     cin >> n; 
  88.     for (int i = 1; i <= n; i++) cin >> a[i]; 
  89.     for (int i = 1; i <= n; i++) cin >> k[i];  
  90.  
  91.     precompute();
  92.  
  93.     dp[n + 1] = suf_dp[n + 1] = 1;  
  94.  
  95.     for (int l = n; l >= 1; l--) {
  96.         dp[l] = add(dp[l], suf_dp[first_r[l] + 1]);
  97.         suf_dp[l] = add(suf_dp[l + 1], dp[l]); 
  98.     }
  99.  
  100.     cout << dp[1] << '\n'; 
  101. }
  102.  
Success #stdin #stdout 0.01s 15856KB
comments (?)
stdin 
4
1 1 2 2
2 1 1 1
stdout 
2
https://ideone.com/l9K0kG
language:
C++14 (gcc 8.3)
created:
1 year 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!