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
#include <bits/stdc++.h>
using namespace std;
int const shift=(1<<20);
int n, m, segTree[2*shift+10];

void query(int l, int r, int col){
    l+=shift-1, r+=shift-1, col--;
    int tmp=(1<<col);
    segTree[l]|=tmp;
    segTree[r]|=tmp;
    while(l/2!=r/2){
        if(l%2==0) segTree[l+1]|=tmp;
        if(r%2==1) segTree[r-1]|=tmp;
        l/=2, r/=2;
    } 
}

int ans(int a=0, int b=shift-1, int l=0, int r=n-1, int u=1, int bt=0){
    if(a>b || r<a || u>2*shift || (bt&(1<<2))) return 0;
    bt|=segTree[u];
    if(a==b && bt==3) {
        return 1; 
    }
    int mid=(a+b)/2;
    int ans1=ans(a, mid, l, r, 2*u, bt), ans2=ans(mid+1, b, l, r, 2*u+1, bt);
    return ans1+ans2;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++){
        int l, r, col;
        scanf("%d %d %d", &l, &r, &col);
        query(l, r, col);
    }
    cout<<ans();    
    return 0;
}