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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <bitset>
#include <iostream>

using namespace std;

int get_max_r(int n) {
  int x = 1;
  while (x < n) {
    x = x << 1;
  }
  return x;
}

typedef unsigned char color;

struct node {
  color c;
  color splited;
};

const color GREEN = 0b011;

node tree[(1 << 21) + 1];
int N;

void stain_rec(int root, int a, int b, int l, int r, color c) {
  node *v = &tree[root];
  if (a == l && b == r) {
    v->c |= c;
  } else {
    int m = (a + b) / 2;
    int lson = root * 2;
    int rson = root * 2 + 1;

    if (l < m) stain_rec(lson, a, m, l, min(r, m), c);
    if (m < r) stain_rec(rson, m, b, max(l, m), r, c);
    v->c |= tree[lson].c & tree[rson].c & c;
    v->splited |= (tree[lson].splited | tree[rson].splited |
                   (tree[lson].c ^ tree[rson].c)) &
                  c;
  }
}

void stain(int l, int r, color c) { stain_rec(1, 0, N, l, r, c); }

int count_green_rec(int root, int a, int b, color parent_c) {
  node *v = &tree[root];
  color c = v->c | parent_c;
  if (!v->splited) {
    if (c == GREEN) return b - a;
    return 0;
  }

  int m = (a + b) / 2;
  int lson = root * 2;
  int rson = root * 2 + 1;
  return count_green_rec(lson, a, m, c) + count_green_rec(rson, m, b, c);
}

int count_green() { return count_green_rec(1, 0, N, 0); }

int main() {
  int i, n, m;
  int l, r, c;

  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  N = get_max_r(n);

  for (int i = 0; i <= N * 2; ++i) {
    tree[i] = {0, false};
  }

  for (i = 0; i < m; ++i) {
    cin >> l >> r >> c;
    stain(l - 1, r, 1 << (c - 1));
  }
  cout << count_green() << endl;
  return 0;
}