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
#include <bits/stdc++.h>
using namespace std;
const int liscie=1048576;
int drzewo[(liscie<<1)+1][4]; 	// bialy:nic  zolty:0  niebieski:1  zielony:2  czerwony:3
bool czerwony[(liscie<<1)+1], zolty[(liscie<<1)+1], niebieski[(liscie<<1)+1];
void przepchnij(int w, int p, int k)
{
	int w1=w<<1, w2=(w<<1)+1;
	czerwony[w1]|=czerwony[w];
	zolty[w1]|=zolty[w];
	niebieski[w1]|=niebieski[w];
	czerwony[w2]|=czerwony[w];
	zolty[w2]|=zolty[w];
	niebieski[w2]|=niebieski[w];
	if (!czerwony[w1])
	{
		if (zolty[w1])
		{
			drzewo[w1][0]=((k-p+1)>>1)-drzewo[w1][1]-drzewo[w1][2]-drzewo[w1][3];
			drzewo[w1][2]+=drzewo[w1][1];
			drzewo[w1][1]=0;
		}
		if (niebieski[w1])
		{
			drzewo[w1][1]=((k-p+1)>>1)-drzewo[w1][0]-drzewo[w1][2]-drzewo[w1][3];
			drzewo[w1][2]+=drzewo[w1][0];
			drzewo[w1][0]=0;
		}
	}
	else
	{
		drzewo[w1][0]=drzewo[w1][1]=drzewo[w1][2]=0;
		drzewo[w1][3]=((k-p+1)>>1);
	}
	if (!czerwony[w2])
	{
		if (zolty[w2])
		{
			drzewo[w2][0]=((k-p+1)>>1)-drzewo[w2][1]-drzewo[w2][2]-drzewo[w2][3];
			drzewo[w2][2]+=drzewo[w2][1];
			drzewo[w2][1]=0;
		}
		if (niebieski[w2])
		{
			drzewo[w2][1]=((k-p+1)>>1)-drzewo[w2][0]-drzewo[w2][2]-drzewo[w2][3];
			drzewo[w2][2]+=drzewo[w2][0];
			drzewo[w2][0]=0;
		}
	}
	else
	{
		drzewo[w2][0]=drzewo[w2][1]=drzewo[w2][2]=0;
		drzewo[w2][3]=((k-p+1)>>1);
	}
	return;
}
int x, y, c;
void update(int w, int p, int k)
{
//	cout<<w<<" "<<p<<" "<<k<<endl;
	if (czerwony[w])
		return;
	if (p>=x && k<=y)
	{
		if (c==1)
		{
			zolty[w]=true;
			drzewo[w][0]=k-p+1-drzewo[w][1]-drzewo[w][2]-drzewo[w][3];
			drzewo[w][2]+=drzewo[w][1];
			drzewo[w][1]=0;	
		}
		else if (c==2)
		{
			niebieski[w]=true;
			drzewo[w][1]=k-p+1-drzewo[w][0]-drzewo[w][2]-drzewo[w][3];
			drzewo[w][2]+=drzewo[w][0];
//			if (drzewo[w][1]<0)
//				cout<<"CO  "<<w<<" "<<p<<" "<<k<<" "<<drzewo[w][0]<<" "<<drzewo[w][2]<<" "<<drzewo[w][3]<<endl;
			drzewo[w][0]=0;
		}
		else
		{
			czerwony[w]=true;
			drzewo[w][0]=drzewo[w][1]=drzewo[w][2]=0;
			drzewo[w][3]=k-p+1;
		}
		return;
	}
	przepchnij(w, p, k);
	int sr=p+k;	sr>>=1;
	if (x<=sr)
	{
		update(w<<1, p, sr);
	}
	if (y>sr)
	{
		update((w<<1)+1, sr+1, k);
	}
	drzewo[w][0]=drzewo[w<<1][0]+drzewo[(w<<1)+1][0];
	drzewo[w][1]=drzewo[w<<1][1]+drzewo[(w<<1)+1][1];
	drzewo[w][2]=drzewo[w<<1][2]+drzewo[(w<<1)+1][2];
	drzewo[w][3]=drzewo[w<<1][3]+drzewo[(w<<1)+1][3];
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;	cin>>n>>m;
	int pliscie=liscie+n;
/*	for (int i=liscie; i<pliscie; i++)
		drzewo[i][0]=1;
	for (int i=liscie-1; i>0; i--)
		drzewo[i][0]=drzewo[(i<<1)+1][0]+drzewo[i<<1][0];*/
	for (int i=0; i<m; i++)
	{
		cin>>x>>y>>c;
		update(1, 1, liscie);
//		cout<<"KORZEN "<<drzewo[1][0]<<" "<<drzewo[1][1]<<" "<<drzewo[1][2]<<endl;
	}
	cout<<drzewo[1][2];
	return 0;
}