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
60
#include <iostream>
using namespace std;

struct Tree {
    int *segments;
    int treeSize;
    Tree(int size) {
        treeSize = 1 << (size + 1);
        segments = new int[treeSize];
        for (int i=0; i<treeSize; i++) segments[i] = 0;
    }

    void update(int start, int end, int current, int globalStart, int globalEnd) {
        if (globalEnd <= start || globalStart >= end || segments[current] > 0) return;
        if (globalStart <= start && globalEnd >= end) {
            segments[current]++;
        }
        if (end - start > 1) {
            int split = (start + end + 1) >> 1;
            update(start, split, 2 * current, globalStart, globalEnd);
            update(split, end, 2 * current + 1, globalStart, globalEnd);
        }
    }

    void add(int start, int end) {
        update(0, treeSize/2, 1, start, end + 1);
    }

    bool marked(int x) {
        return segments[treeSize/2 + x] > 0;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    int treeSize = 0;
    while ((1 << treeSize) - 1 < n) treeSize++;
    Tree yellow = Tree(treeSize);
    Tree blue = Tree(treeSize);
    Tree red = Tree(treeSize);
    for (int i=0; i<m; i++) {
        int s, e, c;
        cin >> s >> e >> c;
        if (c == 1) {
            yellow.add(s, e);
        } else if (c == 2) {
            blue.add(s, e);
        } else {
            red.add(s, e);
        }
    }
    int sum = 0;
    for (int i=1; i<=n; i++) {
        if (yellow.marked(i) && blue.marked(i) && !red.marked(i)) sum++;
    }
    cout << sum << endl;
    return 0;
}