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. // Bài này mấy em cần học qua thuật toán Counting Sort - một thuật toán sắp xếp rất phổ biến
  12. // và kết hợp với Segment Tree để tối ưu thuật toán này
  13. // 26 cây Segment Tree cho 26 chữ cái, tree[c] sẽ quản lí những vị trí i sao cho s[i] = c
  14. const int N = 1e5 + 5;  
  15.  
  16. int n, q; 
  17. string s;  
  18.  
  19. struct SegTree {
  20. 	int n; 
  21. 	vector<int> seg, lazy;   
  22.  
  23. 	SegTree() {}
  24.  
  25. 	SegTree(int n): n(n) {
  26. 		seg.resize(4 * n + 1, 0);   
  27. 		lazy.resize(4 * n + 1, -1); 
  28. 	}
  29.  
  30. 	void push(int id, int l, int r) {
  31. 		if (lazy[id] != -1) {
  32. 			int mid = (l + r) >> 1;
  33.  
  34. 			seg[id * 2] = (mid - l + 1) * lazy[id]; 
  35. 			lazy[id * 2] = lazy[id]; 
  36.  
  37. 			seg[id * 2 + 1] = (r - mid) * lazy[id];  
  38. 			lazy[id * 2 + 1] = lazy[id];  
  39.  
  40. 			lazy[id] = -1;  
  41. 		}
  42. 	}
  43.  
  44. 	void update(int id, int l, int r, int u, int v, int val) {
  45. 		if (l > v || r < u) return;   
  46.  
  47. 		if (u <= l && r <= v) {
  48. 			seg[id] = (r - l + 1) * val;  
  49. 			lazy[id] = val; 
  50. 			return; 
  51. 		}
  52.  
  53. 		push(id, l, r);   
  54.  
  55. 		int mid = (l + r) >> 1; 
  56. 		update(id * 2, l, mid, u, v, val); 
  57. 		update(id * 2 + 1, mid + 1, r, u, v, val); 
  58.  
  59. 		seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  60. 	}
  61.  
  62. 	int get(int id, int l, int r, int u, int v) {
  63. 		if (l > v || r < u) return 0;   
  64.  
  65. 		if (u <= l && r <= v) return seg[id];  
  66.  
  67. 		push(id, l, r);   
  68.  
  69. 		int mid = (l + r) >> 1;  
  70. 		return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  71. 	}
  72. }; 
  73.  
  74. SegTree tree[26]; 
  75.  
  76. int main() {
  77. 	ios::sync_with_stdio(false); 
  78. 	cin.tie(nullptr);  	
  79. 	cin >> n >> q; 
  80. 	cin >> s; 
  81. 	s = ' ' + s;  
  82.  
  83. 	for (int c = 0; c <= 25; c++) tree[c] = SegTree(n);  
  84.  
  85. 	for (int i = 1; i <= n; i++) {
  86. 		tree[s[i] - 'a'].update(1, 1, n, i, i, 1); 
  87. 	}	
  88.  
  89. 	while (q--) {
  90. 		int l, r, type; 
  91. 		cin >> l >> r >> type; 
  92.  
  93. 		vector<int> cnt(26, 0);  
  94. 		for (int c = 0; c <= 25; c++) {
  95. 			cnt[c] = tree[c].get(1, 1, n, l, r);   
  96. 			tree[c].update(1, 1, n, l, r, 0); 
  97. 		}
  98.  
  99. 		if (type == 0) {
  100. 			// non-increasing order
  101. 			for (int c = 25; c >= 0; c--) {
  102. 				tree[c].update(1, 1, n, l, l + cnt[c] - 1, 1);
  103. 				l += cnt[c]; 	
  104. 			}
  105. 		}
  106. 		else {
  107. 			// non-decreasing order
  108. 			for (int c = 0; c <= 25; c++) {
  109. 				tree[c].update(1, 1, n, l, l + cnt[c] - 1, 1);  
  110. 				l += cnt[c]; 
  111. 			}
  112. 		}
  113. 	}
  114.  
  115. 	for (int i = 1; i <= n; i++) {
  116. 		for (int c = 0; c <= 25; c++) {
  117. 			if (tree[c].get(1, 1, n, i, i) == 1) s[i] = c + 'a';    
  118. 		}
  119. 	}
  120.  
  121. 	for (int i = 1; i <= n; i++) cout << s[i]; 
  122. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
stdout
copy 
cbcaaaabdd
https://ideone.com/OE38CG
language:
C++14 (gcc 8.3)
created:
37 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!