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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <set>
#define DEBUG false
using namespace std;
class Zbior {
  size_t n;
  set<pair<size_t, size_t>> przedzialy;
  public:
  Zbior(size_t n) { this->n = n; }
  Zbior(size_t n, set<pair<size_t, size_t>> przedzialy) {
    this->n = n;
    this->przedzialy = przedzialy;
  }
  set<pair<size_t, size_t>>::iterator nastepny(size_t x) {
    return przedzialy.upper_bound({x, -1});
  }
  set<pair<size_t, size_t>>::iterator zawierajacy(size_t x) {
    auto xx = nastepny(x);
    if(xx == przedzialy.begin())
      return przedzialy.end();
    else
      --xx;
    if(xx->first <= x && x <= xx->second)
      return xx;
    return przedzialy.end();
  }
  void usun(size_t a, size_t b) {
    auto prawy = zawierajacy(b);
    if(prawy != przedzialy.end()) {
      size_t dopelnienie = prawy->second;
      przedzialy.erase(prawy);
      if(b != dopelnienie)
        przedzialy.insert({b + 1, dopelnienie});
    }
    auto lewy = zawierajacy(a);
    if(lewy != przedzialy.end()) {
      size_t dopelnienie = lewy->first;
      przedzialy.erase(lewy);
      if(dopelnienie != a)
        przedzialy.insert({dopelnienie, a - 1});
      if(DEBUG)
        cerr << "Obięto lewy koniec\n";
    }
    lewy = prawy = nastepny(a);
    while(prawy != przedzialy.end() && prawy->second <= b)
      ++prawy;
    przedzialy.erase(lewy, prawy);
  }
  Zbior &dodaj(size_t a, size_t b) {
    if(b < a)
      return *this;
    auto lewy = zawierajacy(a - 1);
    if(lewy != przedzialy.end())
      a = lewy->first;  // rozszerzamy do lewej
    auto prawy = zawierajacy(b + 1);
    if(prawy != przedzialy.end())
      b = prawy->second;  // rozszerzamy do prawej
    usun(a, b);           // usuwamy wszystkie w przedziale
    przedzialy.insert({a, b});
    return *this;
  }
  Zbior negacja() {
    set<pair<size_t, size_t>> nowy;
    size_t poprzedni = 0;
    for(auto e : przedzialy) {
      if(e.first != 0) {
        size_t nastepny = e.first - 1;
        if(nastepny >= poprzedni)
          nowy.insert({poprzedni, nastepny});
      }
      poprzedni = e.second + 1;
    }
    if(n - 1 >= poprzedni)
      nowy.insert({poprzedni, n - 1});
    return Zbior(n, nowy);
  }
  Zbior iloczyn(Zbior &inny) {
    Zbior wynikowy(n);
    for(auto e : przedzialy) {
      auto brzeg = e.first;
      while(brzeg <= e.second) {
        auto lewy = inny.zawierajacy(brzeg);
        if(lewy != inny.przedzialy.end()) {
          auto nastepny = min(e.second, lewy->second);
          wynikowy.dodaj(brzeg, nastepny);
          brzeg = lewy->second + 1;
        } else {
          auto nastepny = inny.nastepny(brzeg);
          brzeg = nastepny == inny.przedzialy.end() ? n : nastepny->first;
        }
      }
    }
    return wynikowy;
  }
  size_t dlugosc() {
    size_t s = 0;
    for(pair<size_t, size_t> e : przedzialy) {
      s += e.second - e.first + 1;
    }
    return s;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  size_t n, m;
  cin >> n >> m;  // puszki, operacje
  Zbior zolty(n), niebieski(n), czerwony(n);
  while(m--) {
    size_t l, r, k;
    cin >> l >> r >> k;
    --l;
    --r;
    switch(k) {
      case 1:
        zolty.dodaj(l, r);
        break;
      case 2:
        niebieski.dodaj(l, r);
        break;
      case 3:
        czerwony.dodaj(l, r);
        break;
    }
  }
  cout << czerwony.negacja().iloczyn(zolty).iloczyn(niebieski).dlugosc() << '\n';
  return 0;
}