fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int p = 31; 
  12. const int MOD = 1e9 + 9277;   
  13. const int N = 2e5 + 5;  
  14.  
  15. int n, q;   
  16. string s;  
  17.  
  18. int p_pow[N]; 
  19.  
  20. void precompute() {
  21. 	p_pow[0] = 1;  
  22. 	for (int i = 1; i <= n; i++) p_pow[i] = 1ll * p_pow[i - 1] * p % MOD; 
  23. }
  24.  
  25. struct Node {
  26. 	int len = 0; 
  27. 	int h = 0, h_rev = 0; 
  28.  
  29. 	Node() {}
  30.  
  31. 	Node(char c) {
  32. 		len = 1;  
  33. 		h = h_rev = (c - 'a' + 1); 
  34. 	}
  35.  
  36. 	Node operator+(const Node& other) const {
  37. 		Node ans; 
  38. 		ans.len = len + other.len;  
  39. 		ans.h = (1ll * h * p_pow[other.len] + other.h) % MOD;   
  40. 		ans.h_rev = (1ll * other.h_rev * p_pow[len] + h_rev) % MOD; 
  41. 		return ans; 
  42. 	}
  43. }; 
  44.  
  45. Node seg[4 * N];  
  46.  
  47. void build(int id, int l, int r) {
  48. 	if (l == r) {
  49. 		seg[id] = Node(s[l]);  
  50. 		return; 
  51. 	}
  52. 	int mid = (l + r) >> 1; 
  53. 	build(id * 2, l, mid); 
  54. 	build(id * 2 + 1, mid + 1, r); 
  55. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  56. }
  57.  
  58. void update(int id, int l, int r, int pos, char c) {
  59. 	if (l > pos || r < pos) return; 
  60.  
  61. 	if (l == r) {
  62. 		seg[id] = Node(c); 
  63. 		return; 
  64. 	}
  65.  
  66. 	int mid = (l + r) >> 1; 
  67. 	update(id * 2, l, mid, pos, c); 
  68. 	update(id * 2 + 1, mid + 1, r, pos, c); 
  69.  
  70. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  71. }
  72.  
  73. Node get(int id, int l, int r, int u, int v) {
  74. 	if (l > v || r < u) return Node();  
  75.  
  76. 	if (u <= l && r <= v) return seg[id]; 
  77.  
  78. 	int mid = (l + r) >> 1; 
  79. 	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  80. }
  81.  
  82. int main() {
  83. 	ios::sync_with_stdio(false); 
  84. 	cin.tie(nullptr); 	
  85. 	cin >> n >> q; 	
  86. 	cin >> s; 
  87. 	s = ' ' + s;  
  88.  
  89. 	precompute();  
  90.  
  91. 	build(1, 1, n);  
  92.  
  93. 	while (q--) {
  94. 		int type; cin >> type; 
  95.  
  96. 		if (type == 1) {
  97. 			int pos; char c;  
  98. 			cin >> pos >> c; 
  99. 			update(1, 1, n, pos, c); 
  100. 		}
  101. 		else {
  102. 			int l, r; 
  103. 			cin >> l >> r; 
  104. 			Node cur = get(1, 1, n, l, r); 
  105. 			cout << (cur.h == cur.h_rev ? "YES" : "NO") << '\n'; 
  106. 		}
  107. 	}
  108. }
Success #stdin #stdout 0.01s 13600KB
comments (?)
stdin 
7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5
stdout 
YES
NO
YES
https://ideone.com/LhI4tW
language:
C++14 (gcc 8.3)
created:
338 days 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!