fork download
copy 
  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 MOD = 1007050321; 
  12. const int N = 1e5 + 5; 
  13.  
  14. int n, q; 
  15. string s; 
  16. int pow2[N]; 
  17.  
  18. void precompute() {
  19. 	pow2[0] = 1;  
  20. 	for (int i = 1; i <= n; i++) pow2[i] = 1ll * pow2[i - 1] * 2 % MOD;
  21. }
  22.  
  23. struct Node {
  24. 	int len = 0; 
  25. 	int val = 0; 
  26.  
  27. 	Node() {}
  28.  
  29. 	Node(char c) {
  30. 		len = 1;  
  31. 		val = c - '0'; 
  32. 	}
  33.  
  34. 	Node operator+(const Node& other) const {
  35. 		Node ans; 
  36. 		ans.len = len + other.len; 
  37. 		ans.val = (1ll * val * pow2[other.len] + other.val) % MOD; 
  38. 		return ans; 
  39. 	}
  40. }; 
  41.  
  42. Node seg[4 * N];
  43.  
  44. void build(int id, int l, int r) {
  45. 	if (l == r) {
  46. 		seg[id] = Node(s[l]); 
  47. 		return; 
  48. 	}
  49. 	int mid = (l + r) >> 1; 
  50. 	build(id * 2, l, mid); 
  51. 	build(id * 2 + 1, mid + 1, r); 
  52. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  53. }
  54.  
  55. int findKth(int id, int l, int r, int k) {
  56. 	if (l == r) return l;  
  57. 	int mid = (l + r) >> 1; 
  58. 	if (k <= seg[id * 2].len) {
  59. 		return findKth(id * 2, l, mid, k); 
  60. 	}
  61. 	return findKth(id * 2 + 1, mid + 1, r, k - seg[id * 2].len); 
  62. }
  63.  
  64. void update(int id, int l, int r, int pos) {
  65. 	if (l > pos || r < pos) return; 
  66.  
  67. 	if (l == r) {
  68. 		seg[id] = Node(); 
  69. 		return; 
  70. 	}
  71.  
  72. 	int mid = (l + r) >> 1; 
  73. 	update(id * 2, l, mid, pos); 
  74. 	update(id * 2 + 1, mid + 1, r, pos); 
  75.  
  76. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  77. }
  78.  
  79. Node get(int id, int l, int r, int u, int v) {
  80. 	if (l > v || r < u) return Node();  
  81.  
  82. 	if (u <= l && r <= v) return seg[id]; 
  83.  
  84. 	int mid = (l + r) >> 1; 
  85. 	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  86. }
  87.  
  88. int main() {
  89. 	ios::sync_with_stdio(false); 
  90. 	cin.tie(nullptr); 	
  91. 	cin >> s; 
  92. 	n = s.size(); 
  93. 	s = ' ' + s;  
  94.  
  95. 	precompute();  
  96.  
  97. 	build(1, 1, n);   
  98.  
  99. 	cin >> q; 
  100.  
  101. 	while (q--) {
  102. 		char type; cin >> type; 
  103.  
  104. 		if (type == '-') {
  105. 			int pos; cin >> pos; 
  106. 			pos = findKth(1, 1, n, pos); 
  107. 			update(1, 1, n, pos); 
  108. 		}
  109. 		else {
  110. 			int l, r; 
  111. 			cin >> l >> r; 
  112. 			l = findKth(1, 1, n, l), r = findKth(1, 1, n, r); 
  113. 			cout << get(1, 1, n, l, r).val << '\n'; 
  114. 		}
  115. 	}
  116. }
Success #stdin #stdout 0.01s 6672KB
comments (?)
stdin
copy 
00111
3
? 1 5
- 3
? 3 4
stdout
copy 
7
3
https://ideone.com/33UgG7
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!