【解题报告】Koishi Loves Segments

前言

我已经收到 koishi 打来的电话了

题意

在一个数轴上，给你 n 条线段，同时有 m 个点它突然兴奋(题面这么说的qwq)，认为它只能被覆盖 x 次，求最多能放在数轴上的线段数量

题解

看到这题我也是突然兴奋qwq，然后开始分析
我们需要判断只有 m 个点，显然的我们先对所有的坐标离散化，给每个点赋上权值 -x ，我们将所有的线段都放在数轴上，所有覆盖的位置权值 +1，可以各种方法维护

此时很显然权值为正的点是不合法的，此时转化一下题意，就成了：

• 使用最少的线段覆盖数轴上的点，第 x 个点要求至少覆盖 y 次

贪心选取对于能选择的能达到最远的线段即可，可以用 堆/平衡树/优先队列 等数据结构简单维护
$$
\large\color{grey}{\text{Talk is cheap , show you the code}}
$$

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=400005;
const int inf=0x3f3f3f3f;
int n,m,b[maxn],sum[maxn],ans;
int vis[maxn];
struct node
{
    int pos,val;
}p[maxn];
struct seg
{
    int l,r;
}s[maxn];
vector<int>c[maxn];
priority_queue<int>q;

inline int read(void)
{
    int num,sign=1;char c;
    while(!isdigit(c=getchar()))if(c=='-')sign=0;num=c-'0';
    while(isdigit(c=getchar()))num=(num<<1)+(num<<3)+c-'0';
    return sign?num:-num;
}

signed main(void)
{
    n=read(),m=read();
    for(register int i=1;i<=n;++i)s[i].l=read(),s[i].r=read();
    for(register int i=1;i<=m;++i)b[i]=p[i].pos=read(),p[i].val=read();
    sort(b+1,b+1+m);
    int M=unique(b+1,b+1+m)-b-1;
    for(register int i=1;i<=m;++i)
    {
        p[i].pos=lower_bound(b+1,b+1+M,p[i].pos)-b;
        if(vis[p[i].pos])
        {
            int t=vis[p[i].pos];
            sum[p[i].pos]+=p[t].val,sum[p[i].pos+1]-=p[t].val;
            p[i].val=min(p[i].val,p[t].val);
        }
        vis[p[i].pos]=i;
        sum[p[i].pos]-=p[i].val,sum[p[i].pos+1]+=p[i].val;
    }
    for(register int i=1;i<=n;++i)
    {
        s[i].l=lower_bound(b+1,b+1+M,s[i].l)-b;
        s[i].r=upper_bound(b+1,b+1+M,s[i].r)-b-1;
        ++sum[s[i].l],--sum[s[i].r+1];
        c[s[i].l].push_back(s[i].r);
    }
    for(register int i=1;i<=M;++i)
    {
        sum[i]+=sum[i-1];
        int si=c[i].size();
        for(register int j=0;j<si;++j)q.push(c[i][j]);
        while(sum[i]>0)
        {
            int t=q.top();
            --sum[i],++sum[t+1],--ans;
        }
    }
    cout<<ans+n<<endl;
    return 0;
}