【题解】P11453 [USACO24DEC] Deforestation S

题意

数轴上有 \(n\) 个整点，求最多删除多少个整点，使得 \(k\) 个条件依然满足。每个条件形如：在 \([l_i,r_i]\) 范围内至少存在 \(t_i\) 个整点。

思路

删点操作有悖于满足条件的逻辑，因此正难则反，考虑最少保留多少个点使得所有条件被满足。为了使点数最少，应使每个点贡献的区间尽可能多，不难想到贪心求解，对所有条件的区间按右端点从小到大排序，从右端点往左取点直至满足条件，并更新覆盖这些点的其他区间还需要取的点数。

动态维护区间信息，考虑使用线段树。因值域到达 \(\pm 10^9\)，而区间覆盖又只考虑坐标的大小关系，所以先对坐标离散化。线段树要维护两个信息：该区间已选的点数和该区间最靠右的点。按右端点从小到大枚举每个条件，在该区间中找最靠右的点然后将其删掉，循环往复直至满足要求，继续求解下一条件。最终答案即为总点数 \(n\) 减去取得的点数。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int T,n,k;
int pos[N];
struct Law{int l,r,t;
}lmt[N];
struct Node{int cnt,uns;int l,r;
};
struct Segtr{Node tr[4*N];void push_up(int p){tr[p].cnt=tr[2*p].cnt+tr[2*p+1].cnt;tr[p].uns=max(tr[2*p].uns,tr[2*p+1].uns);}void build(int p,int l,int r){tr[p].l=l,tr[p].r=r;if(l==r){tr[p].cnt=0,tr[p].uns=l;return ;}int mid=(l+r)>>1;build(2*p,l,mid);build(2*p+1,mid+1,r);push_up(p);}void update(int p,int l,int r,int k){if(l==r){tr[p].cnt=1,tr[p].uns=0;return ;}int mid=(l+r)>>1;if(k<=mid) update(2*p,l,mid,k);else update(2*p+1,mid+1,r,k);push_up(p);}Node query(int p,int l,int r){Node val={0,0};if(l<=tr[p].l&&tr[p].r<=r) return tr[p];int mid=(tr[p].l+tr[p].r)>>1;if(l<=mid){Node q=query(2*p,l,r);val.cnt+=q.cnt;val.uns=max(val.uns,q.uns);}if(r>mid){Node q=query(2*p+1,l,r);val.cnt+=q.cnt;val.uns=max(val.uns,q.uns);}return val;}
}seg;
bool cmp(Law x,Law y){return x.r<y.r;
}
int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&pos[i]);sort(pos+1,pos+1+n);for(int i=1;i<=k;i++) scanf("%d%d%d",&lmt[i].l,&lmt[i].r,&lmt[i].t);sort(lmt+1,lmt+1+k,cmp);for(int i=1;i<=k;i++){if(!lmt[i].t) lmt[i].l=lmt[i].r=1,lmt[i].t=0;else{lmt[i].l=(lower_bound(pos+1,pos+1+n,lmt[i].l)-pos);lmt[i].r=(upper_bound(pos+1,pos+1+n,lmt[i].r)-pos)-1;}}seg.build(1,1,n);for(int i=1;i<=k;i++){Node ans=seg.query(1,lmt[i].l,lmt[i].r);while(ans.cnt<lmt[i].t){seg.update(1,1,n,ans.uns);ans=seg.query(1,lmt[i].l,lmt[i].r);}}printf("%d\n",n-seg.query(1,1,n).cnt);}return 0;
}

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