题意
有$n$个点,$m$条线段,每个点最多被覆盖$c_i$次,求最多选择几条线段
数据范围:$1 \le n,m,c_i \le 100000$
题解
先按右端点为第一关键字升序,左端点为第二关键字降序排序
随后按顺序选择区间,能选则选
正确性证明:
- 在右端点相同时,显然左端点越大区间长度越短,结果越优
- 在右端点不同时,对于先选择的区间$i$与和$i$发生冲突的区间$j$,需要讨论的情况为$$l_i < l_j < r_i < r_j$$
此时$[l_j,r_i]$的最小值为$0$(否则不会产生冲突)
若用$j$替换掉$i$,会导致$[l_i,l_j]+1$(但无法利用,因为中间最小值为$0$),$[r_i,r_j]-1$,但答案不变,腾出来的空间没有用,相当于浪费掉了,因此不选更优
可否选择用线段树维护查询即可
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int INF=0x3f3f3f3f;
const int N=100000+10;
int n,m;
int c[N];
int ans;
struct D{
int l,r;
inline bool operator < (const D& x) const{
return r==x.r?l>x.l:r<x.r;
}
} d[N];
struct node{
int w,tag;
} T[N<<2];
inline void pushUp(int rt){
T[rt].w=min(T[ls].w,T[rs].w);
}
inline void pushDown(int rt){
T[ls].w+=T[rt].tag;
T[rs].w+=T[rt].tag;
T[ls].tag+=T[rt].tag;
T[rs].tag+=T[rt].tag;
T[rt].tag=0;
}
void build(int rt,int l,int r){
if(l==r){
T[rt].w=c[l];
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushUp(rt);
}
void update(int rt,int l,int r,int L,int R,int k){
if(l>=L && r<=R){
T[rt].w+=k;
T[rt].tag+=k;
return ;
}
if(T[rt].tag)
pushDown(rt);
int mid=l+r>>1;
if(L<=mid)
update(ls,l,mid,L,R,k);
if(R>mid)
update(rs,mid+1,r,L,R,k);
pushUp(rt);
}
int query(int rt,int l,int r,int L,int R){
if(l>=L && r<=R){
return T[rt].w;
}
if(T[rt].tag)
pushDown(rt);
int res=INF;
int mid=l+r>>1;
if(L<=mid)
res=min(res,query(ls,l,mid,L,R));
if(R>mid)
res=min(res,query(rs,mid+1,r,L,R));
pushUp(rt);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
scanf("%d%d",&d[i].l,&d[i].r);
sort(d+1,d+m+1);
for(int i=1;i<=m;i++){
int t=query(1,1,n,d[i].l,d[i].r);
if(t<=0)
continue;
ans++;
update(1,1,n,d[i].l,d[i].r,-1);
}
printf("%d",ans);
return 0;
}
版权属于:Pelom
本文链接:https://pelom.top/archives/99/
转载时须注明出处及本声明