fork(2) download
  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
stdin
2
AABBBCCCC
5
1 0
2 1
1 0
2 2
1 3
XXYYY
3
1 3
2 3
1 2
stdout
Case 1:
2
1
2
Case 2:
3
1