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