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
#include <bits/stdc++.h>
#define gc getchar
#define gcu getchar_unlocked
#define fi first
#define se second
#define pb push_back
#define mod ((ll)1e9 + 7)
typedef long long ll;
using namespace std;
//===============================================================================================

int n, m, base = 1, ans;
int d[3000009][6];
void dodaj(int ver, int l, int r, int x, int y, int val);
void licz(int ver);

//===============================================================================================
int main()
{
    scanf("%d %d", &n, &m);
    while (base < n)
        base <<= 1;
    for (int i = 0, tempa, tempb, tempc; i < m; i++)
    {
        scanf("%d %d %d", &tempa, &tempb, &tempc);
        dodaj(1, 0, base - 1, tempa - 1, tempb - 1, tempc);
    }
    licz(1);
    printf("%d\n", ans);
}
//===============================================================================================
// 9 5
// 2 8 1
// 4 5 2
// 6 7 3
// 5 6 2
// 1 2 2
void dodaj(int ver, int l, int r, int x, int y, int val)
{
    if (l > y || r < x)
        return;
    if (l >= x && r <= y)
    {
        d[ver][val] = 1;
        return;
    }
    dodaj(ver * 2, l, (l + r) / 2, x, y, val);
    dodaj(ver * 2 + 1, (l + r) / 2 + 1, r, x, y, val);
}
void licz(int ver)
{
    if (ver >= base)
    {
        if (d[ver][1] && d[ver][2] && !d[ver][3])
            ans++;
        return;
    }
    d[ver * 2][1] |= d[ver][1];
    d[ver * 2][2] |= d[ver][2];
    d[ver * 2][3] |= d[ver][3];
    d[ver * 2 + 1][1] |= d[ver][1];
    d[ver * 2 + 1][2] |= d[ver][2];
    d[ver * 2 + 1][3] |= d[ver][3];
    licz(ver * 2);
    licz(ver * 2 + 1);
}