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>

const int N = 200005;

int id[N], val[N], min[N], max[N], add[N], pri[N], n, k, t, ans;
int lc[N], rc[N];
void setadd(int x, int v) {
	min[x] += v, max[x] += v, add[x] += v, val[x] += v;
}
void pushdown(int x) {
	if (add[x]) setadd(lc[x], add[x]), setadd(rc[x], add[x]), add[x] = 0;
}
void pushup(int x) {
	min[x] = max[x] = val[x];
	if (lc[x]) min[x] = std::min(min[x], min[lc[x]]), max[x] = std::max(max[x], max[lc[x]]);
	if (rc[x]) min[x] = std::min(min[x], min[rc[x]]), max[x] = std::max(max[x], max[rc[x]]);
}
void split(int now, int k, int &x, int &y) {
	if (!now) return void(x = y = 0);
	pushdown(now);
	if (id[now] <= k)
		x = now, split(rc[x], k, rc[x], y);
	else
		y = now, split(lc[y], k, x, lc[y]);
	pushup(now);
}
int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (pri[x] < pri[y])
		return pushdown(x), rc[x] = merge(rc[x], y), pushup(x), x;
	else
		return pushdown(y), lc[y] = merge(x, lc[y]), pushup(y), y;
}

int root;
void dfs(int &x, int k) {
	if (!x) return;
	if (min[x] == max[x] && min[x] == k - 1) return setadd(x, 1);
	pushdown(x);
	dfs(lc[x], k), dfs(rc[x], k);
	if (val[x] == k - 1) return val[x] += 1, pushup(x);
	x = merge(lc[x], rc[x]);
}
void count(int x) {
	if (!x) return;
	pushdown(x);
	if (val[x] == k) ++ans;
	count(lc[x]), count(rc[x]);
}
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::srand(std::time(0));
	std::cin >> n >> k >> t;
	for (int i = 1; i <= n; ++i)
		pri[i] = std::rand(), id[i] = i, pushup(i), root = merge(root, i);
	for (int i = 1; i <= t; ++i) {
		int l, r, g;
		std::cin >> l >> r >> g;
		int a, b;
		split(root, r, root, b);
		split(root, l - 1, a, root);
		dfs(root, g);
		root = merge(a, merge(root, b));
	}
	count(root);
	std::cout << ans << '\n';
	return 0;
}