1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
5.
6. vector<unsigned long long> t;
7. vector<unsigned long long> codes;
8. const unsigned long long prime = 61;
9. vector<unsigned long long> pows;
10.
11. void build (int v, int tl, int tr) {
12. if (tl == tr){
13. t[v] = codes[tl] * pows[tl - 1];
14. }
15. else {
16. int tm = (tl + tr) / 2;
17. build (2 * v, tl, tm);
18. build (2 * v + 1, tm + 1, tr);
19. t[v] = t[2 * v] + t[2 * v + 1];
20. }
21. }
22.
23. unsigned long long sum (int v, int tl, int tr, int l, int r) {
24. if (l > r){
25. //cout << "here";
26. return 0;
27. }
28. if (l == tl && r == tr)
29. return t[v];
30. int tm = (tl + tr) / 2;
31. return sum (2 * v, tl, tm, l, min(r, tm))
32. + sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
33. }
34.
35. void update (int v, int tl, int tr, int pos, unsigned long long newVal) {
36. if (tl == tr)
37. t[v] = newVal * pows[pos - 1];
38. else {
39. int tm = (tl + tr) / 2;
40. if (pos <= tm)
41. update (v*2, tl, tm, pos, newVal);
42. else
43. update (2 * v + 1, tm + 1, tr, pos, newVal);
44. t[v] = t[2 * v] + t[2 * v + 1];
45. }
46. }
47.
48. int main() {
49. ios_base::sync_with_stdio(false);
50. cin.tie(NULL);
51. int n, k;
52. cin >> n >> k;
53. t.resize(4 * n);
54. string a;
55. cin >> a;
56. codes.resize(n + 1);
57. for(int i = 1; i <= n; i++){
58. codes[i] = a[i - 1] - 'A' + 1;
59. }
60. pows.resize(n + 1);
61. pows[0] = 1;
62. for(int i = 1; i <= n; i++){
63. pows[i] = pows[i - 1] * prime;
64. }
65. build(1, 1, n);
66. cin.ignore();
67. for(int t = 0; t < k; t++){
68. char q;
69. cin >> q;
70. if(q == '?'){
71. int i, j, len;
72. cin >> i >> j >>len;
73. if(i > j){
74. swap(i, j);
75. }
76. if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){
77. cout << "+";
78. }
79. else{
80. cout << "-";
81. }
82. }
83. else if(q == '*'){
84. int temp;
85. char c;
86. cin >> temp >> c;
87. update(1, 1, n, temp, c - 'A' + 1);
88. }
89. cin.ignore();
90. }
91. return 0;
92. }
Runtime error #stdin #stdout 0s 4240KB
stdin
Standard input is empty
stdout
Standard output is empty