二分+线段树

O(nlog²n)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n;
struct node{
	int l,r,t;
}s[N];


bool cmp(node x,node y){
	return x.r==y.r?x.l>y.r:x.r<y.r;
}

struct trnode{
	int l,r,sum1,sum2,add;
}tr[4*N];

#define ls(p) (p<<1)
#define rs(p) (p<<1|1)

void pushup(int p){
	tr[p].sum1=tr[ls(p)].sum1+tr[rs(p)].sum1;
	tr[p].sum2=tr[ls(p)].sum2+tr[rs(p)].sum2;
}

void pushdown(int p){
	if(tr[p].add){
		tr[ls(p)].sum1=tr[ls(p)].r-tr[ls(p)].l+1;
		tr[rs(p)].sum1=tr[rs(p)].r-tr[rs(p)].l+1;
		tr[ls(p)].sum2=0;
		tr[rs(p)].sum2=0;
		tr[ls(p)].add=tr[p].add;
		tr[rs(p)].add=tr[p].add;
	}
	tr[p].add=0;
}

void build(int p,int l,int r){
	
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].sum1=0;
		tr[p].sum2=1;
		return ;
	}
	int m=l+r>>1;
	build(ls(p),l,m);
	build(rs(p),m+1,r);
	pushup(p);
}

void change(int p,int l,int r){
	if(r<tr[p].l||l>tr[p].r)return ;
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].sum1=tr[p].r-tr[p].l+1;
		tr[p].sum2=0;
		tr[p].add=1;
		return ;
	}
	pushdown(p);
	int m=tr[p].l+tr[p].r>>1;
	if(l<=m)change(ls(p),l,r);
	if(r>m)change(rs(p),l,r);
	pushup(p);
}

int query(int p,int l,int r,int k){
	if(r<tr[p].l||l>tr[p].r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return k==1?tr[p].sum1:tr[p].sum2;
	pushdown(p);	
	int m=tr[p].l+tr[p].r>>1;
	return query(ls(p),l,r,k)+query(rs(p),l,r,k);
}

int find(int R,int k){
	int l=1,r=R;
	while(l<=r){
		int m=l+r>>1;
		if(query(1,m,R,0)>k)l=m+1;
		else r=m-1;
	}
	return l;
}//二分查找 

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int k;
		memset(tr,0,sizeof(tr));
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
		sort(b+1,b+n+1);
		int blen=unique(b+1,b+n+1)-b-1;
		
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(b+1,b+blen+1,a[i])-b;
		}
		
		for(int i=1;i<=k;i++){
			int l,r,t;
			scanf("%d%d%d",&l,&r,&t);
			l=lower_bound(b+1,b+blen+1,l)-b;
			r=upper_bound(b+1,b+blen+1,r)-b-1;
			s[i]={l,r,t};
		}
		
		sort(s+1,s+k+1,cmp);
		
		int ans=0;
		build(1,1,blen);
		for(int i=1;i<=k;i++){
			int k=query(1,s[i].l,s[i].r,1);
			if(k<s[i].t){
				int l=find(s[i].r,s[i].t-k);
				change(1,l,s[i].r);
				ans+=s[i].t-k;
			}
		}
		printf("%d",n-ans);
		printf("\n");
	}
}

scy代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m;
vector< pair<int, int> > G[N];
int a[N],dis[N];bool vis[N];

void spfa()
{
    for (int i = 0; i <= n; ++i)dis[i] = -1e9;
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(0);
    dis[0] = 0;
    while(!q.empty())
    {
        int x = q.front();q.pop();vis[x] = 0;
        for (auto i: G[x])
        {
            int y = i.first, w = i.second;
            if (dis[y] < dis[x] + w)
            {
                dis[y] = dis[x] + w;
                if (!vis[y])
                {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}
int main()
{
    int T;scanf("%d", &T);
    while(T--){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    for(int i=0;i<=n;i++)G[i].clear();
    sort(a+1,a+n+1);
    for (int i = 1,l, r, w; i <= m; ++i)
    {
        scanf("%d%d%d", &l, &r, &w); 
        l = lower_bound(a+1,a+n+1,l) - a;
        r = upper_bound(a+1,a+n+1,r) - a-1;
        G[l-1].push_back({r,w});//  p[l-1]+w<= p[r]
    }
    for (int i = 0; i < n; ++i)
    {
        G[i].push_back({i+1,0}); // p[i]+0 <= p[i+1]
        G[i+1].push_back({i,-1}); // p[i]+1 >= p[i+1] -> p[i+1] -1 <= p[i]
    }
    spfa();
    printf("%d\n", n-dis[n]);
    }
    return 0;
}