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
#include <cstdio>

int n, m;
int a, b, c;
int N;

short tree[2097152];
short yellow = 1;
short blue = 2;
short red = 4;
short green = yellow + blue;
short brown = yellow + blue + red;

void addhelper(int b, int e, short col)
{
    if (b == e) return;

    int bf = b/2; int ef = e/2;
    if (bf != ef)
    {
        if (b % 2 == 0) tree[b+1] |= col;
        if (e % 2 == 1) tree[e-1] |= col;
    }
    
    if ((tree[bf*2] & col) == col && (tree[bf*2+1] & col) == col) tree[bf] |= col;
    if ((tree[ef*2] & col) == col && (tree[ef*2+1] & col) == col) tree[ef] |= col;

    addhelper(bf, ef, col);
}

void add(int beg, int end, short col)
{
    tree[N + beg] |= col;
    tree[N + end] |= col;
    addhelper(N + beg, N + end, col);
}

int countGreen(int poz, int size, int col)
{
    if (poz > 2*N) return 0;
    if (poz == 6)
    {
        int t = 1;
    }

    if (((tree[poz] | col) ^ green) == 0) return size;
    if (poz >= N) return 0;
    return countGreen(poz*2, size/2, (tree[poz] | col)) + countGreen(poz*2+1, size/2, (tree[poz] | col));
}

int countBrown(int poz, int size, int col)
{
    if (poz > 2*N) return 0;
    if (poz == 6)
    {
        int t = 1;
    }

    if (((tree[poz] | col) ^ brown) == 0) return size;
    if (poz >= N) return 0;
    return countBrown(poz*2, size/2, (tree[poz] | col)) + countBrown(poz*2+1, size/2, (tree[poz] | col));
}

int main()
{
    scanf("%d %d",&n,&m);
    N = 1; while(N < n) N*=2;

    for (int j = 0; j < m; j++)
    {
        scanf("%d %d %d",&a,&b,&c);
        if (c == 1) add(a-1, b-1, 1);
        if (c == 2) add(a-1, b-1, 2);
        if (c == 3) add(a-1, b-1, 4);
    }

    int cg = countGreen(1, N, 0) - countBrown(1, N, 0);
    printf("%d\n",cg);
}