fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5;  
  12.  
  13. int n;  
  14. int a[N]; 
  15.  
  16. int last[N]; 
  17. int nxt[N]; 
  18.  
  19. struct PersistentSegTree {
  20. 	struct Node {
  21. 		int l = 0, r = 0;   
  22. 		int sum = 0;  
  23. 	}; 
  24.  
  25. 	int n; 
  26. 	vector<Node> seg; 
  27.  
  28. 	PersistentSegTree(int n) : n(n) {
  29. 		seg.push_back(Node());
  30. 	}
  31.  
  32. 	int update(int pre, int l, int r, int pos, int val) {
  33. 		int cur = seg.size();  
  34. 		seg.push_back(seg[pre]); 
  35. 		if (l == r) {
  36. 			seg[cur].sum += val; 
  37. 			return cur; 
  38. 		}
  39. 		int mid = (l + r) >> 1; 
  40. 		if (pos <= mid) {
  41. 			seg[cur].l = update(seg[pre].l, l, mid, pos, val); 
  42. 		}
  43. 		else {
  44. 			seg[cur].r = update(seg[pre].r, mid + 1, r, pos, val); 
  45. 		}
  46. 		int lc = seg[cur].l, rc = seg[cur].r; 
  47. 		seg[cur].sum = seg[lc].sum + seg[rc].sum; 
  48. 		return cur;
  49. 	}
  50.  
  51. 	int getKth(int rt, int l, int r, int k) {
  52. 		if (seg[rt].sum < k) return n + 1; 
  53. 		if (l == r) return l; 
  54. 		int mid = (l + r) >> 1; 
  55. 		int lc = seg[rt].l, rc = seg[rt].r; 
  56. 		if (k <= seg[lc].sum) {
  57. 			return getKth(lc, l, mid, k); 
  58. 		}
  59. 		return getKth(rc, mid + 1, r, k - seg[lc].sum); 
  60. 	}
  61.  
  62. 	int update(int pre, int pos, int val) {
  63. 		return update(pre, 1, n, pos, val); 
  64. 	}
  65.  
  66. 	int getKth(int rt, int k) {
  67. 		return getKth(rt, 1, n, k); 
  68. 	}
  69. };
  70.  
  71. int root[N]; 
  72.  
  73. int main() {
  74. 	ios::sync_with_stdio(false); 
  75. 	cin.tie(nullptr); 	
  76. 	cin >> n; 
  77. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  78.  
  79. 	for (int x = 1; x <= n; x++) last[x] = n + 1; 
  80. 	for (int i = n; i >= 1; i--) {
  81. 		nxt[i] = last[a[i]];   
  82. 		last[a[i]] = i;  
  83. 	}
  84.  
  85. 	PersistentSegTree pst(n); 
  86. 	for (int i = n; i >= 1; i--) {
  87. 		root[i] = root[i + 1]; 
  88. 		root[i] = pst.update(root[i], i, 1);
  89. 		if (nxt[i] <= n) root[i] = pst.update(root[i], nxt[i], -1); 
  90. 	}
  91.  
  92. 	for (int k = 1; k <= n; k++) {
  93. 		int ans = 0;  
  94. 		int i = 1;  
  95. 		while (i <= n) {
  96. 			i = pst.getKth(root[i], k + 1); 
  97. 			++ans; 
  98. 		}
  99. 		cout << ans << ' '; 
  100. 	}
  101. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
1 3 4 3 3
stdout
copy 
3 1 1 1 1
https://ideone.com/14aBVC
language:
C++14 (gcc 8.3)
created:
14 days 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!