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
82
83
84
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1048576;
int t[MAX_N * 2][5]; // 0 - bialy, 1 - zolty, 2 - niebieski, 3 - zielony, 4 - cokolwiek z czerwonym
int n, m, T_BASE=1;

void update(const int &node, const int &nodel, const int &noder, const int &l, const int &r, const int &k)
{
    //fprintf(stderr, "update(node=%d, nodel=%d, noder=%d, l=%d, r=%d, k=%d), ", node, nodel, noder, l, r, k);
    int node_range_size = noder - nodel + 1;
    int fixed = -1;
    for (int i=0; i<5; ++i)
        if (t[node][i] == node_range_size)
            fixed = i;
    //fprintf(stderr, "fixed = %d\n", fixed);
    if (nodel == l and r == noder and k == 4) {
        for (int i=0; i<5; ++i)
            t[node][i] = 0;
        t[node][4] = node_range_size;
        return;
    }
    if (0 <= fixed) {
        // cale poddrzewo mialo kontakt z czerownym => nothing to do
        if (fixed == 4)
            return;
        // cale poddrzewo jest dokladnie tego samego koloru => nothing to do
        if (fixed == k)
            return;
        // cale poddrzewo jest zielone => tylko pomaranczowy moze je zmienic
        if (fixed == 3 and k != 4)
            return;
        
        if (nodel == l and r == noder) {
            // we have to update only this node
            t[node][fixed] = 0;
            if (k == 4)
                t[node][k] = node_range_size;
            else
                t[node][fixed+k] = node_range_size;
            return;
        } else {
            // trzeba "zrzucic" wartosci do poddrzewa
            for (int i=0; i<5; ++i)
                t[2*node][i] = t[2*node+1][i] = t[node][i] / 2;
        }
    }
    int half = (nodel + noder) / 2; // noder of left child
    if (l <= half)
        update(2*node, nodel, half, l, min(half, r), k);
    ++half; // nodel of right child
    if (half <= r)
        update(2*node+1, half, noder, max(half, l), r, k);

    // recalcuate t[node] using its children
    for (int i=0; i<5; ++i)
        t[node][i] = t[2*node][i] + t[2*node+1][i];
    //fprintf(stderr, "t[%d] = (%d, %d, %d, %d, %d)\n", node, t[node][0], t[node][1], t[node][2], t[node][3], t[node][4]);
}

void init_t()
{
    t[1][0] = T_BASE;
}

int main()
{
    scanf("%d %d", &n, &m);
    while (T_BASE < n)
        T_BASE *= 2;
    init_t();
    int l, r, k;
    while (m--) {
        scanf("%d %d %d", &l, &r, &k);
        if (k == 3)
            k = 4;
        --l; --r;
        //fprintf(stderr, "(%d, %d, %d)\n", l, r, k);
        update(1, 0, T_BASE-1, l, r, k);
    }
    printf("%d\n", t[1][3]);
    return 0;
}