题目描述
????在课余会接受一些民间的鹰眼类委托，即远距离的狙击监视防卫。
????一共接到了?份委托，这些委托与?个直线排布的监视点相关。
第?份委托的内容为：对于区间[??, ??]中的监视点，至少要防卫其中的??个。
????必须完成全部委托，并且希望选取尽量少的监视点来防卫。
输入描述:
第一行，两个正整数?，?。
接下来?行，每行三个整数??，??，??。
输出描述:
一行，一个整数，即所需防卫的最少监视点数量。
示例1
输入
复制
11 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出
复制
6

直观的贪心不难想到，如果我们按照右端点R从小到大排序之后，因为我们是按照右端点排序的，那么必然每次从右边开始放置一定是最优的。

所以我们有以下直观做法：

  1. 先对区间按照R从小到大排序。
  2. 用线段树维护总区间的放置信息。
  3. 每次对于一个查询，查看当前的查询区间已经放置的个数，若大于等于需要的，直接跳过。否则需要放置，那么二分找到最靠右的需要放置的总个数的位置，然后把这个区间全部标记为已经放置过即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=5e5+10;
int n,m,res;
struct node{
	int l,r,k;
}q[N<<1];
struct seg{
	int l,r,sum,lazy;
}t[N<<2];
int cmp(node a,node b){
	return a.r==b.r?a.k>b.k:a.r<b.r;
}
inline void push_up(int p){
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
inline void push_down(int p){
	if(t[p].lazy){
		t[p<<1].lazy=t[p<<1|1].lazy=t[p].lazy;
		t[p<<1].sum=(t[p<<1].r-t[p<<1].l+1);
		t[p<<1|1].sum=(t[p<<1|1].r-t[p<<1|1].l+1);
		t[p].lazy=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(l==r)	return ; int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r){
		t[p].sum=(r-l+1);	t[p].lazy=1;	return ;
	}
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r);
	else if(l>mid)	change(p<<1|1,l,r);
	else	change(p<<1,l,mid),change(p<<1|1,mid+1,r);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].sum;
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return ask(p<<1,l,mid)+ask(p<<1|1,mid+1,r);
	push_up(p);
}
int bsearch(int k,int up){
	int l=1,r=up;
	while(l<r){
		int mid=l+r+1>>1;
		if(up-mid+1-ask(1,mid,up)>=k)	l=mid;
		else	r=mid-1;	
	}
	return l;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)	scanf("%lld %lld %lld",&q[i].l,&q[i].r,&q[i].k);
	sort(q+1,q+1+m,cmp); build(1,1,n);
	for(int i=1;i<=m;i++){
		int num=ask(1,q[i].l,q[i].r);
		if(num>=q[i].k)	continue;
		res+=q[i].k-num;	change(1,bsearch(q[i].k-num,q[i].r),q[i].r);
	}
	cout<<res<<endl;
	return 0;
}