暑假的救赎day5 有一个事情是贪心没太讲出来啊 浅说一下，对于任意数量k的牛，你可以拆成k组数量为1的牛，所以你根本不用去思考数量问题 所以问题退化成了有多少个区间可以堆在这个要求的区间内，用线段树去统计当前这段处理区间内还可以填几个，把能填的填进来 贪心策略是以右端点排序，本质上是贪心。证明看课程视频！

#include <bits/stdc++.h>
using namespace std;

int n,k,c;
struct Node{
	int sign = 0,mx = 0;
};
struct Qu{
	int l,r,de;
};
Qu a1[50005];
Node a[200005];
bool cmp(Qu x,Qu y)
{
	if(x.r == y.r)
	{
		return x.l < y.l;
	}
	return x.r < y.r;
}
void push_down(int k)
{
	a[k*2].sign += a[k].sign;
	a[k*2+1].sign += a[k].sign;
	a[k*2].mx += a[k].sign;
	a[k*2+1].mx += a[k].sign;
	a[k].sign = 0;
}
void push_up(int k)
{
	a[k].mx = max(a[k*2].mx,a[k*2+1].mx); 
}
void add(int k,int l,int r,int s,int t,int sp)
{
	if(s <= l && r <= t)
	{
		a[k].sign += sp;
		a[k].mx += sp;
		return;
	}
	if(a[k].sign)
	    push_down(k);
	int mid = (l + r) /2;
	if(s <= mid) add(k*2,l,mid,s,t,sp);
	if(t > mid) add(k*2+1,mid+1,r,s,t,sp);
	push_up(k);
}
int find(int k,int l,int r,int s,int t)
{
	if(s <= l && r <= t)
	{
		return a[k].mx;
	}
	if(a[k].sign)
	    push_down(k);
	int maxn = -1;
	int mid = (l + r)/2;
	if(s <= mid) maxn = max(maxn , find(k*2,l,mid,s,t));
	if(t > mid) maxn = max(maxn, find(k*2+1,mid+1,r,s,t));
	return maxn;
}
int main()
{
	cin >> k >> n >> c;
	for(int i=1; i <= k ;i++)
	{
		cin >> a1[i].l >> a1[i].r >> a1[i].de;
	}
	sort(a1+1,a1+k+1,cmp);
	int ans = 0;
	for(int i=1; i <= k ;i++)
	{
		int b = find(1,1,n,a1[i].l,a1[i].r-1);
		add(1,1,n,a1[i].l,a1[i].r-1,min(c-b,a1[i].de));
		ans += min(c-b,a1[i].de);
	}
	cout << ans;
}

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
using namespace std;
const int N=20005;
int n,m,k,s,t,c,ans;
struct node1{
	int l,r,k;
	bool operator<(const node1 &k)const{
		return r<k.r;
	}
}a[N*3];
struct node{
	int mx[N<<2],sign[N<<2];
	void down(int p){
		if (!sign[p]) return;
		sign[p<<1]+=sign[p];mx[p<<1]+=sign[p];
		sign[p<<1|1]+=sign[p];mx[p<<1|1]+=sign[p];
		sign[p]=0;
	}
	void update(int p){
		mx[p]=max(mx[p<<1],mx[p<<1|1]);
	}
	void add(int p,int l,int r,int s,int t,int k){
	// 区间[s,t] +k
		if (l>=s && r<=t){
			sign[p]+=k;
			mx[p]+=k; 
			return;
		} 
		down(p);
		if (s<=mid) add(p<<1,l,mid,s,t,k);
		if (t>mid) add(p<<1|1,mid+1,r,s,t,k);
		update(p);
	}
	int query(int p,int l,int r,int s,int t){
	//查询区间最大值 
		if (l>=s && r<=t) return mx[p];
		down(p);
		int xx=0;
		if (s<=mid) xx=query(p<<1,l,mid,s,t);
		if (t>mid) xx=max(xx,query(p<<1|1,mid+1,r,s,t));
		return xx;	
	}
}T;
int main(){
	cin>>k>>n>>c;
	for (int i=1;i<=k;++i){
		cin>>a[i].l>>a[i].r>>a[i].k;
		a[i].r-=1;
	}
	//按区间右端点排序 
	sort(a+1,a+1+k);
	for (int i=1;i<=k;++i){
		//计算出区间最大值 
		int maxn=T.query(1,1,n,a[i].l,a[i].r);  
		//能选择的奶牛数量=min(c-maxn,该组奶牛的数量) 
		int p=min(c-maxn,a[i].k);
		ans+=p;//累加答案 
		T.add(1,1,n,a[i].l,a[i].r,p);//区间增加p 
	}
	cout<<ans;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e4+10;
int n,k,ans,c;
struct Line{
	int m,l,r;
	bool operator<(const Line& l2)const{
		return r < l2.r;
	}
}line[MAXN];
int zt[MAXN];
int tree[MAXN<<2],tag[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return lc(x)|1;}
void push_up(int);
void push_down(int);
int query(int,int,int,int,int);
void update(int,int,int,int,int,int);
int main(){
	scanf("%d%d%d",&k,&n,&c);
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&line[i].l,&line[i].r,&line[i].m);
	}
	sort(line+1,line+1+k);
	for(int i=1;i<=k;i++){
		int l = line[i].l,r = line[i].r,m = line[i].m;
		//max [l,r)
		int maxn = query(1,1,n,l,r-1);
		int chose =((c-maxn) < m)?(c-maxn):m;
		ans += chose;
		//[l,r) += chose
		update(1,1,n,l,r-1,chose);
	}
	cout<<ans;
	return 0;
}
void push_up(int x){
	tree[x] = max(tree[lc(x)],tree[rc(x)]);
}
void push_down(int x){
	tree[lc(x)] += tag[x];
	tree[rc(x)] += tag[x];
	tag[lc(x)] += tag[x];
	tag[rc(x)] += tag[x]; 
	tag[x] = 0; 
}
int query(int x,int l,int r,int ql,int qr){
	if(ql <= l && qr >= r){
		return tree[x];
	}
	int mid = (l+r)>>1;
	int ans = 0;
	push_down(x);
	if(ql <= mid){
		ans = max(ans,query(lc(x),l,mid,ql,qr));
	}
	if(qr > mid){
		ans = max(ans,query(rc(x),mid+1,r,ql,qr));
	}
	push_up(x);
	return ans;
}
void update(int x,int l,int r,int ql,int qr,int value){
	if(ql <= l && qr >= r){
		tree[x] += value;
		tag[x] += value;
		return;
	}
	int mid = (l+r)>>1;
	push_down(x);
	if(ql <= mid){
		update(lc(x),l,mid,ql,qr,value);
	}
	if(qr > mid){
		update(rc(x),mid+1,r,ql,qr,value);
	}
	push_up(x);
}