题解：CF1260D A Game with Traps

#include<bits/stdc++.h>
#define int long long 
#define Maxn 400005 
using namespace std;
int a[Maxn];
struct node {
	int l,r,d;
	bool operator<(const node&is)
	const {return l != is.l?l < is.l:r < is.r;}
} e[Maxn],t[Maxn];
signed main()
{
	int m,n,k,t1;
	cin>>m>>n>>k>>t1;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	sort(a+1,a+1+m);
	for(int i=1;i<=k;i++)
		cin>>e[i].l>>e[i].r>>e[i].d;
	int l = 0,r = 4e5+5,mid;
	while(l < r) {
		int tot = 0;
		mid = (l+r)>>1;
		for(int i=1;i<=k;i++)
			if(e[i].d >= mid)
				t[++tot] = e[i];
		sort(t+1,t+1+tot);
		int ans = 0;
		for(int i=1;i<=tot;i++)  {
			int l1 = t[i].l,r1 = t[i].r;
//			cout<<i<<"|";
			while(i < tot&&t[i+1].l <= r1)r1 = max(r1,t[++i].r);
			ans += (r1-l1+1)*2;
//			cout<<l1<<" "<<r1<<"]\n";
		}
//		cout<<mid<<" "<<ans+n+1<<"\n";
		if(ans+n+1 <= t1)r = mid;
		else l = mid+1;
	} int maxn = 0;
	for(int i=1;i<=k;i++)
		if(e[i].d < l)
			maxn = max(maxn,e[i].d);
	l = 0,r = m;
	while(l < r) {
		mid = (l+r+1)>>1;
		if(a[mid] < maxn)l = mid;
		else r = mid-1;
	}
//	cout<<a[l]<<" "<<maxn<<" ";
	cout<<m-l;
	return 0;
}