Advertisement
Guest User

Untitled

a guest
Nov 29th, 2014
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. char *str(char *dest, char *src, int m, int n)
  5. {
  6. int i;
  7. char *temp = dest;
  8. for(i = 0; i<n;++i) dest[m + i] = src[i];
  9. return temp;
  10. }
  11. /*int opr(char p)
  12. {
  13. int i, k = 1;
  14. for(i = 0; i < p - 97; ++i) k*= 2;
  15. return k;
  16. }*/
  17. void build(int *t, char *a, int v, int l, int r)
  18. {
  19. if(l == r) t[v] = 1<< (a[l] - 97);
  20. else {
  21. int m = (l + r)/2;
  22. build(t, a, v * 2, l, m);
  23. build(t, a, v * 2 + 1 , m + 1, r);
  24. t[v] = (t[v * 2]) ^ (t[v * 2 + 1]);
  25. }
  26. }
  27. void SegmentTree_Build(char *a, int *t, int n)
  28. {
  29. int i;
  30. //for(i = 0; i < 4 * n; ++i) t[i] = 0;
  31. build(t, a, 1, 0, n - 1);
  32. }
  33. int query(int *t, int l, int r, int v, int a, int b)
  34. {
  35. if(l == a && r == b) return t[v];
  36. else{
  37. int m = (a + b)/2;
  38. if(r <= m) return query(t, l, r, v * 2, a, m);
  39. else {
  40. if (l > m) return query(t , l , r, v * 2 + 1, m + 1, b);
  41. else return query(t, l, m, v * 2, a, m) ^ query(t, m + 1, r, v * 2 + 1, m + 1, b);
  42. }
  43. }
  44. }
  45. int SegmentTree_Query(int *t, int n, int l, int r)
  46. {
  47. int k = query(t, l, r, 1, 0, n - 1);
  48. return k;
  49. }
  50. void update(int *t, int i, char d, int v, int a, int b)
  51. {
  52. if(a == b) t[v] = 1<<(d - 97);
  53. else{
  54. int m = (a + b)/2;
  55. if(i <= m) update(t, i, d, v * 2, a, m);
  56. else update(t, i, d, v * 2 + 1, m + 1, b);
  57. t[v] = t[v * 2] ^ t[v * 2 + 1];
  58. }
  59. }
  60. void SegmentTree_Update(int *t, int i, char *d, int m, int n)
  61. {
  62. int j;
  63. for(j = 0; j < m;++j, ++i) update(t, i, d[j], 1, 0, n - 1);
  64. }
  65. int main(int argc, char **argv)
  66. {
  67.  
  68. int i, n, m, r, l, k;
  69. char p[4];
  70. p[3] = 0;
  71. char *b = (char*)malloc(1000001 * sizeof(char));
  72. char *a = (char*)malloc(1000001 * sizeof(char));
  73. gets(a);
  74. n = strnlen(a, 1000001);
  75. int *t = (int*)malloc(4 * n * sizeof(int));
  76. int log2n = -1;
  77. for(;1<<(log2n + 1) <= n; ++log2n);
  78. //t = (int*)malloc(4 * n * sizeof(int));
  79. SegmentTree_Build(a,t,n);
  80. //free(a);
  81. scanf("%d", &m);
  82. for(i = 0; i < m;++i){
  83. scanf("%s", p);
  84. if(p[0] == 'H'){
  85. scanf("%d%d", &l, &r);
  86. k = SegmentTree_Query(t, n, l, r);
  87. //printf("%d,k", k);
  88. if(((k - 1) & k) == 0 || k == 0) printf("YES\n");
  89. else printf("NO\n");
  90. } else {
  91. scanf("%d ", &l);
  92. gets(b);
  93. r = strnlen(b, 1000001);
  94. a = str(a, b, l, r);
  95. if(n < log2n * r) SegmentTree_Update(t, l, b, r, n);
  96.  
  97. else SegmentTree_Build(a,t, n);
  98.  
  99. //printf("%d %d\n", r, l);
  100. //a = str(a, b, l, r);
  101.  
  102. //SegmentTree_Update(t, l, b, r, n);
  103.  
  104. }
  105. }
  106. free(b);
  107. free(a);
  108. free(t);
  109. return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement