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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int R = 3e6 + 5;

bool p[R][4];
int ile[R][5];

int n, m;
int rozm = 1;

void push(int gdzie){
	if(p[gdzie][1]){
		p[2 * gdzie][1] = true;
		p[2 * gdzie + 1][1] = true;
		p[gdzie][1] = false;
		
		ile[2 * gdzie][1] += ile[2 * gdzie][0];
		ile[2 * gdzie][0] = 0;
		ile[2 * gdzie][3] += ile[2 * gdzie][2];
		ile[2 * gdzie][2] = 0;
		
		ile[2 * gdzie + 1][1] += ile[2 * gdzie + 1][0];
		ile[2 * gdzie + 1][0] = 0;
		ile[2 * gdzie + 1][3] += ile[2 * gdzie + 1][2];
		ile[2 * gdzie + 1][2] = 0;
	}
	
	if(p[gdzie][2]){
		p[2 * gdzie][2] = true;
		p[2 * gdzie + 1][2] = true;
		p[gdzie][2] = false;
		
		ile[2 * gdzie][2] += ile[2 * gdzie][0];
		ile[2 * gdzie][0] = 0;
		ile[2 * gdzie][3] += ile[2 * gdzie][1];
		ile[2 * gdzie][1] = 0;
		
		ile[2 * gdzie + 1][2] += ile[2 * gdzie + 1][0];
		ile[2 * gdzie + 1][0] = 0;
		ile[2 * gdzie + 1][3] += ile[2 * gdzie + 1][1];
		ile[2 * gdzie + 1][1] = 0;
	}
	
	if(p[gdzie][3]){
		p[2 * gdzie][3] = true;
		p[2 * gdzie + 1][3] = true;
		p[gdzie][3] = false;
		
		ile[2 * gdzie][4] += ile[2 * gdzie][0] + ile[2 * gdzie][1] + ile[2 * gdzie][2] + ile[2 * gdzie][3];
		for(int i = 0; i <= 3; i++) ile[2 * gdzie][i] = 0;
		
		ile[2 * gdzie + 1][4] += ile[2 * gdzie + 1][0] + ile[2 * gdzie + 1][1] + ile[2 * gdzie + 1][2] + ile[2 * gdzie + 1][3];
		for(int i = 0; i <= 3; i++) ile[2 * gdzie + 1][i] = 0;
	}
}

void insert(int gdzie, int pocz, int kon, int x, int y, int rodzaj){
	if(x <= pocz && kon <= y){
		int bia = ile[gdzie][0], zol = ile[gdzie][1], nie = ile[gdzie][2];
		int zie = ile[gdzie][3];
		
		if(rodzaj == 0) ile[gdzie][0]++;
		
		else if(rodzaj == 1){
			ile[gdzie][1] += bia;
			ile[gdzie][0] = 0;
			ile[gdzie][3] += nie;
			ile[gdzie][2] = 0;
		}
		
		else if(rodzaj == 2){
			ile[gdzie][2] += bia;
			ile[gdzie][0] = 0;
			ile[gdzie][3] += zol;
			ile[gdzie][1] = 0;
		}
		
		else{
			ile[gdzie][4] += bia + zol + nie + zie;
			for(int i = 0; i <= 3; i++) ile[gdzie][i] = 0;
		}
		
		p[gdzie][rodzaj] = true;
		return;
	}
	push(gdzie);
	int sr = (pocz + kon) / 2;
	if(x <= sr) insert(2 * gdzie, pocz, sr, x, y, rodzaj);
	if(sr < y) insert(2 * gdzie + 1, sr + 1, kon, x, y, rodzaj);
	
	for(int i = 0; i <= 4; i++){
		ile[gdzie][i] = ile[2 * gdzie][i] + ile[2 * gdzie + 1][i];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	
	while(rozm < n) rozm *= 2;
	
	for(int i = 1; i <= n; i++){
		insert(1, 1, rozm, i, i, 0);
	}
	
	for(int i = 1; i <= m; i++){
		int l, r, k;
		cin >> l >> r >> k;
		insert(1, 1, rozm, l, r, k);
	}
	
	cout << ile[1][3];
}