fork download
copy 
  1. #include <stdio.h>
  2. int N, Q, c, lp, rp, seg[262144][2];
  3. void query1(int a, int b, int k, int l, int r) {
  4. 	if (r <= a || b <= l) return;
  5. 	if (a <= l && r <= b) {
  6. 		int p = k, d = r - l; seg[k][0] = (r - l) - seg[k][0], seg[k][1]++;
  7. 		while (p > 1) {
  8. 			p >>= 1; d <<= 1;
  9. 			seg[p][0] = seg[2 * p][0] + seg[2 * p + 1][0];
  10. 			if (seg[p][1] % 2 == 1) seg[p][0] = d - seg[p][0];
  11. 		}
  12. 	}
  13. 	else {
  14. 		query1(a, b, 2 * k, l, (l + r) / 2);
  15. 		query1(a, b, 2 * k + 1, (l + r) / 2, r);
  16. 	}
  17. }
  18. int query2(int a, int b, int k, int l, int r) {
  19. 	if (r <= a || b <= l) return 0;
  20. 	if (a <= l && r <= b) {
  21. 		int ret = seg[k][0], p = k;
  22. 		while (p > 1) {
  23. 			p >>= 1;
  24. 			if (seg[p][1] % 2 == 1) ret = (r - l) - ret;
  25. 		}
  26. 		return ret;
  27. 	}
  28. 	int lc = query2(a, b, 2 * k, l, (l + r) / 2);
  29. 	int rc = query2(a, b, 2 * k + 1, (l + r) / 2, r);
  30. 	return lc + rc;
  31. }
  32. int main() {
  33. 	scanf("%d%d", &N, &Q);
  34. 	for (int i = 0; i < Q; i++) {
  35. 		scanf("%d%d%d", &c, &lp, &rp);
  36. 		if (c == 1) query1(lp, rp, 1, 0, 131072);
  37. 		else printf("%d\n", query2(lp, rp, 1, 0, 131072));
  38. 	}
  39. 	return 0;
  40. }
Success #stdin #stdout 0s 5508KB
comments (?)
stdin
copy 
8 4
1 3 7
2 2 5
1 2 4
2 1 6
stdout
copy 
2
3
https://ideone.com/Kn5ypG
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!