Problem: Example

Input

3 2
3
1 2 1
2 3 2
3 3 1


Output

1

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
typedef pair<int, bool> sP;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<ll> vec;

struct SegT {
private:
	int n; vector<int> node;vector<P> lazy;
	vector<bool> valid,avalid;
	const ll init_c = INF;
public:
	SegT(int sz) {
		n = 1;
		while (n < sz)n <<= 1;
		node.resize(2 * n - 1, 0);
		lazy.resize(2 * n - 1, { -1,-1 });
		valid.resize(2 * n - 1, true);
		avalid.resize(2 * n - 1, true);
	}
	bool lazymerge(P &fr,P &to) {
		if (to.first < 0) {
			to = fr;
		}
		else {
			if (to.second + 1 == fr.first) {
				to.second = fr.second;
			}
			else {
				return false;
			}
		}
		return true;
	}
	void eval(int k, int l, int r) {
		if (lazy[k].first >= 0) {
			//cout << k << " " << node[k] << " " << lazy[k].first << " " << lazy[k].second << endl;
			if (node[k] + 1 == lazy[k].first) {
				node[k] = lazy[k].second;
			}
			else {
				avalid[k] = false;
			}
			if (r - l > 1) {
				if (!lazymerge(lazy[k], lazy[2 * k + 1])) {
					valid[2 * k + 1] = false;
				}
				if (!lazymerge(lazy[k], lazy[2 * k + 2])) {
					valid[2 * k + 2] = false;
				}
			}
		}
		lazy[k] = { -1,-1 };
	}
	void add(int x, int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return;
		if (a <= l && r <= b) {
			lazy[k] = { x,x };
			eval(k, l, r);
		}
		else {
			add(x, a, b, k * 2 + 1, l, (l + r) / 2);
			add(x, a, b, k * 2 + 2, (l + r) / 2, r);
		}
	}
	void clear_lazy() {
		queue<pair<int, P>> q; q.push({ 0,{0,n} });
		while (!q.empty()) {
			int k = q.front().first;
			int l = q.front().second.first;
			int r = q.front().second.second;
			q.pop();
			eval(k, l, r);
			if (r - l > 1) {
				int mid = (l + r) / 2;
				q.push({ 2 * k + 1,{l,mid} });
				q.push({ 2 * k + 2,{mid,r} });
				if (!valid[k]) {
					valid[2 * k + 1] = false;
					valid[2 * k + 2] = false;
				}
			}
		}
	}
	int ans(int sz,int k) {
		int res = 0;
		rep(i, sz) {
			if (!avalid[i + n - 1]) {
				valid[i + n - 1] = false;
			}
			//cout << valid[i + n - 1] << " " << node[i + n - 1] << endl;
			if (valid[i + n - 1] && node[i + n - 1] == k)res++;
		}
		return res;
	}
};

void solve() {
	int n, k; cin >> n >> k;
	int t; cin >> t;
	SegT st(n);
	rep(i, t) {
		int l, r, x; cin >> l >> r >> x; l--; r--;
		st.add(x, l, r+1);
	}
	st.clear_lazy();
	int ans = st.ans(n, k);
	cout << ans << endl;

}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(7);
	//init();
	solve();
	//stop
	return 0;
}