#include <bits/stdc++.h> using namespace std; class tree { int size; vector<int> mask; public: tree(int n) { for (size = 1; size < n; size *= 2); mask.assign(2*size, 0); } void add(int b, int e, int c) { b += size; e += size; while (b/2 != e/2) { if (b % 2 == 1) { mask[b++] |= c; } if (e % 2 == 1) { mask[--e] |= c; } b /= 2; e /= 2; } if (b != e) { mask[b] |= c; } } void flush() { for (int i = 1; i < size; i++) { mask[2*i] |= mask[i]; mask[2*i+1] |= mask[i]; } } int count(int val) { int res = 0; for (int i = 0; i < size; i++) { res += mask[size + i] == val; } return res; } }; int main() { int n, m; scanf("%d %d", &n, &m); tree T(n); while (m--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); T.add(a-1, b, 1 << (c-1)); } T.flush(); printf("%d\n", T.count(3)); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <bits/stdc++.h> using namespace std; class tree { int size; vector<int> mask; public: tree(int n) { for (size = 1; size < n; size *= 2); mask.assign(2*size, 0); } void add(int b, int e, int c) { b += size; e += size; while (b/2 != e/2) { if (b % 2 == 1) { mask[b++] |= c; } if (e % 2 == 1) { mask[--e] |= c; } b /= 2; e /= 2; } if (b != e) { mask[b] |= c; } } void flush() { for (int i = 1; i < size; i++) { mask[2*i] |= mask[i]; mask[2*i+1] |= mask[i]; } } int count(int val) { int res = 0; for (int i = 0; i < size; i++) { res += mask[size + i] == val; } return res; } }; int main() { int n, m; scanf("%d %d", &n, &m); tree T(n); while (m--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); T.add(a-1, b, 1 << (c-1)); } T.flush(); printf("%d\n", T.count(3)); } |