题意

有$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/

转载时须注明出处及本声明