Problem: Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200010
#define INF 1000000000
struct node
{
	int l,r,mx,mn,tg;
}t[MAXN*4];
int cnt,n,k,rt,tm,ans;
void Build(int &i,int l,int r)
{
	if(i==0) i=++cnt;
	if(l==r)
	{
		t[i].l=t[i].r=t[i].mx=t[i].mn=t[i].tg=0;
		return;
	}
	int mid=(l+r)>>1;
	Build(t[i].l,l,mid);
	Build(t[i].r,mid+1,r);
}
void PushDown(int i)
{
	if(t[i].tg)
	{
		int l=t[i].l,r=t[i].r,c=t[i].tg;
		if(l) t[l].tg+=c,t[l].mx+=c,t[l].mn+=c;
		if(r) t[r].tg+=c,t[r].mx+=c,t[r].mn+=c;
		t[i].tg=0;
	}
}
void PushUp(int i)
{
	t[i].mx=max(t[t[i].l].mx,t[t[i].r].mx);
	t[i].mn=min(t[t[i].l].mn,t[t[i].r].mn);
}
void Solve(int &i,int l,int r,int x)
{
	if(i==0) return;
	if(t[i].mn==x-1&&t[i].mx==x-1)
	{
		t[i].tg++;t[i].mx++,t[i].mn++;
		return;
	}
	if(t[i].mn>=x&&t[i].mx<x-1)
	{
		i=0;
		return;
	}
	PushDown(i);
	int mid=(l+r)>>1;
	Solve(t[i].l,l,mid,x);
	Solve(t[i].r,mid+1,r,x);
	PushUp(i);
	if(t[i].l==0&&t[i].r==0) i=0;
}
void Modify(int &i,int l,int r,int L,int R,int x)
{
	if(i==0) return;
	if(L<=l&&r<=R)
	{
		Solve(i,l,r,x);
		return;
	}
	PushDown(i);
	int mid=(l+r)>>1;
	if(L<=mid) Modify(t[i].l,l,mid,L,R,x);
	if(R>mid) Modify(t[i].r,mid+1,r,L,R,x);
	PushUp(i);
	if(t[i].l==0&&t[i].r==0) i=0;
}
void dfs(int i,int l,int r)
{
	if(i==0||t[i].mx<k) return;
	if(l==r)
	{
		if(t[i].mx==k) ans++;
		return;
	}
	PushDown(i);
	int mid=(l+r)>>1;
	dfs(t[i].l,l,mid);
	dfs(t[i].r,mid+1,r);
}
int main()
{
	t[0].mx=-INF;
	t[0].mn=INF;
	t[0].l=t[0].r=t[0].tg=0;
	scanf("%d%d%d",&n,&k,&tm);
	Build(rt,1,n);
	int l,r,x;
	while(tm--)
	{
		scanf("%d%d%d",&l,&r,&x);
		Modify(rt,1,n,l,r,x);
	}
	dfs(rt,1,n);
	printf("%d\n",ans);
}