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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define FORE(x, b, e) for(int x = b; x <= (e); ++x)
#define FORL(x, b, e) for(int x = b; x <  (e); ++x)

#define P(x) cout <<#x <<'=' <<(x) <<" ";
#define PP cout <<endl;
#define Pv(x,a,b) cout << #x<<'=';for(int i=a;i<=b;i++)cout<<' '<<x[i];PP
#define Pv2(x,b) cout << #x<<'=';for(int i=0;i<2*b;i++)cout<<' '<<x[i];PP
#define Pvv(x,y,a,b) cout <<#x <<#y <<'=';FORE(i,a,b)cout<<' '<<x[y[i]];PP

#define MAX 1000000
int red[2*MAX], R=0;
int blu[2*MAX], B=0;
int yel[2*MAX], Y=0;
int gre[2*MAX], T[MAX], G=0;

int compress(int N, int op[])
{
	int n=N;
	if(!N) return 0;
	
	for(int i=0; i<n; i++) T[i]=i;
	std::sort(T, T+n, [op](int i, int j){
		if (op[2*i]!=op[2*j]) return op[2*i] < op[2*j];
		return op[2*i+1] > op[2*j+1];
	});

	n=0;
	gre[2*n]  =op[2*T[0]];
	gre[2*n+1]=op[2*T[0]+1];
	for(int i=1; i<N; i++){
		if (gre[2*n+1]>=op[2*T[i]]){
			gre[2*n+1]=max(gre[2*n+1],op[2*T[i]+1]);
		} else {
			n++;
			gre[2*n]  =op[2*T[i]];
			gre[2*n+1]=op[2*T[i]+1];
		}
	}
	n++;
	for(int i=0; i<2*n; i++) op[i]=gre[i];
	
	return n;
}
int YBmerge(){
	int n=0,y=0,b=0;
	while((y<Y)&&(b<B)){
		if(yel[2*y+1]-1<blu[2*b]) {y++; continue; }
		if(blu[2*b+1]-1<yel[2*y]) {b++; continue; }
		gre[2*n  ]=max(blu[2*b  ],yel[2*y  ]);
		gre[2*n+1]=min(blu[2*b+1],yel[2*y+1]);
		n++;
		if(blu[2*b+1]==yel[2*y+1]) {b++;y++;}
		else
		if(blu[2*b+1]<yel[2*y+1]) b++; else y++;
	}
	return n;
}
	
int brown_delete(){
	int n=0,g=0,r=0;
	while((g<G)&&(r<R)){
//**/P(g);P(gre[2*g]);P(gre[2*g+1]);P(r);P(red[2*r]);P(red[2*r+1]);PP;
		if(gre[2*g+1]-1<red[2*r]) 	{n+=gre[2*g+1]-gre[2*g]; g++; continue; }
		if(red[2*r+1]-1<gre[2*g]) 	{r++; continue; }
		if(gre[2*g]<=red[2*r]) 		n+=red[2*r]-gre[2*g];
		if(red[2*r+1]>=gre[2*g+1]) {g++; continue; }
		gre[2*g]=red[2*r+1];
		r++;
		if(gre[2*g]>=gre[2*g+1]) g++;
	}
//**/P(g);P(G);P(r);P(R);P(n);PP;
	for(;g<G;g++)  n+=gre[2*g+1]-gre[2*g];
	return n;
}
int main()
{
	std::ios_base::sync_with_stdio(false);  cin.tie(NULL);
	
	int p,o;	
	cin >>p >>o;

	for(int i=0; i<o; i++) {
		int l,r,k;
		cin >>l >>r >>k;
		r++;
		if(k==1)			{yel[2*Y]=l; yel[2*Y+1]=r; Y+=1;}
		else if(k==2)	{blu[2*B]=l; blu[2*B+1]=r; B+=1;}
		else				{red[2*R]=l; red[2*R+1]=r; R+=1;}
		
	}
	
//**/Pv2(yel,Y);Pv2(blu,B);Pv2(red,R);Pv2(gre,G);
	Y=compress(Y,yel);
	R=compress(R,red);
	B=compress(B,blu);
	G=YBmerge();
//**/Pv2(yel,Y);Pv2(blu,B);Pv2(red,R);Pv2(gre,G);
	cout <<(brown_delete())<<endl;
	return 0;
}