Problem: Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const function<P(P, P)> minQ = [](P l, P r) { return min(l, r); };

template <typename T>
class LazySegmentTree {
	using func_t = function<T(T, T)>;
	const int n;
	const T id1, id2;
	func_t merge;
	func_t change;
	vector<T> data, lazy;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	void propa(int node) {
		if (lazy[node] == id2) return;
		if (node < n) {
			lazy[node * 2] = change(lazy[node * 2], lazy[node]);
			lazy[node * 2 + 1] = change(lazy[node * 2 + 1], lazy[node]);
		}
		data[node] = change(data[node], lazy[node]);
		lazy[node] = id2;
	}
	void suc(int l, int r, int node, int lb, int ub, T val) {
		if (ub <= l || r <= lb) return;
		propa(node);
		if (l <= lb && ub <= r) {
			lazy[node] = val;
			return;
		}
		int c = (lb + ub) / 2;
		suc(l, r, node * 2, lb, c, val);
		suc(l, r, node * 2 + 1, c, ub, val);
		data[node] = merge(change(data[node * 2], lazy[node * 2]), change(data[node * 2 + 1], lazy[node * 2 + 1]));
	}
	T sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return id1;
		propa(node);
		if (l <= lb && ub <= r) {
			return data[node];
		}
		int c = (lb + ub) / 2;
		return merge(sub(l, r, node * 2, lb, c), sub(l, r, node * 2 + 1, c, ub));
	}
public:
	LazySegmentTree(int n_, T id1_, T id2_, func_t merge_, func_t change_)
		: n(size(n_)), id1(id1_), id2(id2_), merge(merge_), change(change_), data(n * 2, id1), lazy(n * 2, id2) {}
	void update(int l, int r, T val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T find(int l) {
		sub(l, l + 1, 1, 0, n);
		return data[l + n];
	}
};

int main()
{
	cin.sync_with_stdio(false);
	int N, K, T;
	cin >> N >> K >> T;
	LazySegmentTree<P> lst(N, P(0, 0), P(-1, -1), minQ, [](P l, P r) {
		if (l == P(-1, -1)) return r;
		if (r == P(-1, -1)) return l;
		if (l == P(-2, -2) || r == P(-2, -2)) return P(-2, -2);
		return l.second == r.first ? P(l.first, r.second) : P(-2, -2);
	});
	for (int i = 0, l, r, x; i < T; i++) {
		cin >> l >> r >> x; l--; r--;
		lst.update(l, r, P(x - 1, x));
	}
	int res = 0;
	for (int i = 0; i < N; i++) {
		if (lst.find(i) == P(0, K)) {
			res++;
		}
	}
	cout << res << endl;
	return 0;
}