[CC-MCHEF]MasterChef

题目大意：

\(n(n\le10^5)\)片花，第\(i\)片花的美观度为\(b_i(|b_i|\le10^9)\)。总体美观度为各片花的美观度之和。

由于有些花太丑了，要把它们除掉。有\(m\)位工人，第\(i\)位工人只会除编号在\(l_i\)和\(r_i\)之间的花，且每除一片花，收费\(c_i\)元。总共有\(k\)元的资金预算，问工人除完花后，总体美观度最大是多少。

思路：

首先计算不除掉的答案。

线段树求区间最小值以后可以得到移除每个花的代价，然后背包就行了。

时间复杂度\(\mathcal O(n\log n+nk)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg|=ch=='-';

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return neg?-x:x;

}

typedef long long int64;

const int N=1e5+1,K=501;

int b[N];

int64 f[K];

class SegmentTree {

	#define _left <<1

	#define _right <<1|1

	#define mid ((b+e)>>1)

	private:

		int val[N<<2];

	public:

		void build(const int &p,const int &b,const int &e) {

			val[p]=INT_MAX;

			if(b==e) return;

			build(p _left,b,mid);

			build(p _right,mid+1,e);

		}

		void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) {

			if(b==l&&e==r) {

				val[p]=std::min(val[p],x);

				return;

			}

			if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),x);

			if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,x);

		}

		int query(const int &p,const int &b,const int &e,const int &x) const {

			int ret=val[p];

			if(b==e) return ret;

			if(x<=mid) ret=std::min(ret,query(p _left,b,mid,x));

			if(x>mid) ret=std::min(ret,query(p _right,mid+1,e,x));

			return ret;

		}

	#undef _left

	#undef _right

	#undef mid

};

SegmentTree t;

int main() {

	for(register int T=getint();T;T--) {

		const int n=getint(),k=getint(),m=getint();

		std::fill(&f[0],&f[k]+1,0);

		int64 ans=0;

		for(register int i=1;i<=n;i++) {

			b[i]=getint();

			ans+=b[i];

		}

		t.build(1,1,n);

		for(register int i=0;i<m;i++) {

			const int l=getint(),r=getint(),c=getint();

			t.modify(1,1,n,l,r,c);

		}

		for(register int i=1;i<=n;i++) {

			if(b[i]>=0) continue;

			const int c=t.query(1,1,n,i);

			for(register int j=k;j>=c;j--) {

				f[j]=std::max(f[j],f[j-c]-b[i]);

			}

		}

		printf("%lld\n",ans+f[k]);

	}

	return 0;

}