fork(2) download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. const int MX = 2e5 + 5;
  5. char A[MX], B[MX];
  6. int n, q, p[MX], r[MX], sz[MX], ans[30], query[MX][2], res[MX];
  7.  
  8. void init() {
  9. 	for(int i = 0; i < MX; p[i] = i, r[i] = 0, sz[i] = 1, i++);
  10. 	memset(ans, 0, sizeof(ans));
  11. }
  12.  
  13. int find_par(int x) {
  14. 	return (p[x] == x) ? x : p[x] = find_par(p[x]);
  15. }
  16.  
  17. int union_set(int i, int j) {
  18. 	int x = find_par(i), y = find_par(j);
  19. 	if(x != y) {
  20. 		if(r[x] < r[y])
  21. 			swap(x, y);
  22. 		p[y] = x;
  23. 		sz[x] += sz[y];
  24. 		if(r[x] == r[y]) r[x]++;
  25. 		return sz[x];
  26. 	}
  27. 	return 0;
  28. }
  29.  
  30. int main() {
  31. 	int t;
  32. 	char ch;
  33. 	scanf("%d", &t);
  34. 	for(int i = 1; i <= t; i++) {
  35. 		scanf("%c", &ch);
  36. 		scanf("%s %d", A, &q);
  37. 		strcpy(B, A);
  38. 		for(int j = 0; j < q; j++) {
  39. 			scanf("%d %d", &query[j][0], &query[j][1]);
  40. 			if(query[j][0] == 2) A[query[j][1]] = '#';
  41. 		}
  42.  
  43. 		int m = strlen(A); init();
  44. 		for(int j = 0; j < m; j++) {
  45. 			if(A[j] == '#') continue;
  46. 			for(; (j < m) && (A[j] == A[j + 1]); j++) {
  47. 				int val = union_set(j, j + 1);
  48. 				ans[A[j] - 'A'] = max(val, ans[A[j] - 'A']);
  49. 			}
  50. 			ans[A[j] - 'A'] = max(1, ans[A[j] - 'A']);
  51. 		}
  52.  
  53. 		int id = 0;
  54. 		for(int j = q - 1; j >= 0; j--) {
  55. 			if(query[j][0] == 1) {
  56. 				res[id++] = ans[B[query[j][1]] - 'A'];
  57. 			} else {
  58. 				A[query[j][1]] = B[query[j][1]];
  59. 				if(query[j][1] - 1 >= 0) {
  60. 					if(A[query[j][1]] == A[query[j][1] - 1]) {
  61. 						int val = union_set(query[j][1], query[j][1] - 1);
  62. 						ans[A[query[j][1]] - 'A'] = max(val, ans[A[query[j][1]] - 'A']);
  63. 					}
  64. 				}
  65.  
  66. 				if(query[j][1] + 1 < m) {
  67. 					if(A[query[j][1]] == A[query[j][1] + 1]) {
  68. 						int val = union_set(query[j][1], query[j][1] + 1);
  69. 						ans[A[query[j][1]] - 'A'] = max(val, ans[A[query[j][1]] - 'A']);
  70. 					} 
  71. 				}
  72.  
  73. 				ans[A[query[j][1]] - 'A'] = max(1, ans[A[query[j][1]] - 'A']);
  74. 			}
  75. 		}
  76.  
  77. 		printf("Case %d:\n", i);
  78. 		for(int j = id - 1; j >= 0; j--) {
  79. 			printf("%d\n", res[j]);
  80. 		}
  81. 	}
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 6144KB
comments (?)
stdin
copy 
2
AABBBCCCC
5
1 0
2 1
1 0
2 2
1 3
XXYYY
3
1 3
2 3
1 2
stdout
copy 
Case 1:
2
1
2
Case 2:
3
1
https://ideone.com/zXToOA
language:
C++14 (gcc 8.3)
created:
4 years 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!