fork download
copy 
  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. // Bài này mấy em cần học qua thuật toán Counting Sort - đây là một thuật toán sắp xếp phổ biến
  11. // Và kết hợp với Segment Tree để tối ưu thuật toán này
  12. // 26 cây Segment Tree cho 26 chữ cái, seg[c] sẽ quản lí những vị trí i sao cho s[i] = c
  13.  
  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 seg[26]; 
  75.  
  76. int main() {
  77. 	ios::sync_with_stdio(0); cin.tie(0);  	
  78. 	cin >> n >> q; 
  79. 	cin >> s; 
  80. 	s = ' ' + s;  
  81.  
  82. 	for (int c = 0; c <= 25; c++) seg[c] = segTree(n);  
  83.  
  84. 	for (int i = 1; i <= n; i++) {
  85. 		seg[s[i] - 'a'].update(1, 1, n, i, i, 1); 
  86. 	}	
  87.  
  88. 	while (q--) {
  89. 		int l, r, type; 
  90. 		cin >> l >> r >> type; 
  91.  
  92. 		vector<int> cnt(26, 0);  
  93. 		for (int c = 0; c <= 25; c++) {
  94. 			cnt[c] = seg[c].get(1, 1, n, l, r);   
  95. 			seg[c].update(1, 1, n, l, r, 0); 
  96. 		}
  97.  
  98. 		if (type == 0) {
  99. 			// non-increasing order
  100. 			for (int c = 25; c >= 0; c--) {
  101. 				seg[c].update(1, 1, n, l, l + cnt[c] - 1, 1);
  102. 				l += cnt[c]; 	
  103. 			}
  104. 		}
  105. 		else {
  106. 			// non-decreasing order
  107. 			for (int c = 0; c <= 25; c++) {
  108. 				seg[c].update(1, 1, n, l, l + cnt[c] - 1, 1);  
  109. 				l += cnt[c]; 
  110. 			}
  111. 		}
  112. 	}
  113.  
  114. 	for (int i = 1; i <= n; i++) {
  115. 		for (int c = 0; c <= 25; c++) {
  116. 			if (seg[c].get(1, 1, n, i, i) == 1) s[i] = c + 'a';    
  117. 		}
  118. 	}
  119.  
  120. 	for (int i = 1; i <= n; i++) cout << s[i]; 
  121. }
Success #stdin #stdout 0.01s 5284KB
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/IWO2Pv
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!