题面

挂个 pdf
题面下载

算法

有点像扫描线?

容易想到离散化坐标点, 那么对于离散化之后的坐标 \(x\), 粗略来看, 其能分开区间的个数即为 \(\displaystyle\sum_{i = 1}^{n} \left[{l_i < x < R_i}\right]\)
这个可以用类似于差分的方法解决, 每次对于一个区间 \(\left(l_i, r_i\right)\) , 将其区间整体加 \(1\)
发现到可以用差分, 即将差分数组的 \(l_i + 1\) 位置加 \(1\), \(r_i\) 位置减 \(1\)
于是可以直接在离散化时按照 \(l_i + 1\) 和 \(r_i\) 离散化

然后操作的时候需要注意: 离散化前后对应的区间长度改变
我使用 \(Back\) 数组记录离散化之前的真实坐标

对于每一个离散化之后的点, 都可以计算出其被覆盖的次数(差分数组求前缀和), 关键问题就在于怎么去对应到原序列上
可以发现(以下均为离散化之后的点) \(i, i + 1, i \in [1, \rm{farthest \text{ } position})\) 这两个点能够组成一个区间, 对于区间中的数, 其覆盖次数即为差分数组前缀和 \(i\) 的位置, 这个画画图就能出来
也就是说, 对于离散化之后的每一个位置, 我们依次计算前缀和相等的区间, 然后进行排序并处理

于是就可以写代码了

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e5 + 20;
const int MAXSIZE = 2e5 + 20;

int T;
int n, m;

struct node
{
    int Left, Right;
} Sec[MAXN];
int Pos[MAXSIZE];
int Pos_cnt = 0;
int Back[MAXSIZE];

void lsh()
{
    std::sort(Pos + 1, Pos + 2 * n + 1);
    Pos_cnt = std::unique(Pos + 1, Pos + 2 * n + 1) - (Pos + 1);

    for (int i = 1; i <= n; i++)
    {
        int Now_Left = std::lower_bound(Pos + 1, Pos + Pos_cnt + 1, Sec[i].Left) - Pos;
        Back[Now_Left] = Sec[i].Left;
        Sec[i].Left = Now_Left;

        int Now_Right = std::lower_bound(Pos + 1, Pos + Pos_cnt + 1, Sec[i].Right) - Pos;
        Back[Now_Right] = Sec[i].Right;
        Sec[i].Right = Now_Right;
    }
}

int Dif[MAXSIZE]; // 差分数组

struct operation
{
    int Val; // 覆盖次数
    int Len; // 对应原序列上的长度
} Cut[MAXSIZE];
bool cmp(operation a, operation b) { return a.Val > b.Val; }

int solve()
{
    /*离散化后, 对差分数组进行计算*/
    memset(Dif, 0, sizeof(Dif));
    int MaxPos = 0, Ans = 0;
    for (int i = 1; i <= n; i++)
    {
        Dif[Sec[i].Right]--;
        Dif[Sec[i].Left]++;
        MaxPos = std::max(std::max(MaxPos, Sec[i].Right), Sec[i].Left);
    }

    /*覆盖次数计算*/
    for (int i = 1; i <= MaxPos; i++)
    {
        Cut[i].Val = Cut[i - 1].Val + Dif[i];
        if(i != 1)
        {
            Cut[i].Len = Back[i] - Back[i - 1];
        }
    }
    std::sort(Cut + 1, Cut + MaxPos + 1, cmp);


    for (int i = 1; i <= MaxPos; i++)
    {
        int Cut_Num = std::min(m, Cut[i].Len);
        m -= Cut_Num;
        Ans += Cut_Num * Cut[i].Val;
    }

    return Ans;
}

signed main()
{

    scanf("%lld", &T);
    for (int Case = 1; Case <= T; Case++)
    {
        scanf("%lld %lld", &n, &m);
        Pos_cnt = 0;

        for (int i = 1; i <= n; i++)
        {
            /*这里的 Sec 可以理解成对差分数组操作的区间*/
            scanf("%lld %lld", &Sec[i].Left, &Sec[i].Right);
            Pos[++Pos_cnt] = ++Sec[i].Left;
            Pos[++Pos_cnt] = Sec[i].Right;
        }

        lsh();

        printf("case #%lld: %lld\n", Case, solve() + n);
    }

    return 0;
}

/*
2
3 1
1 3
2 4
1 4
3 3
1 3
2 4
1 4

Case #1: 5
Case #2: 7
*/

总结

一般要离散化的题, 如果不好处理, 可以考虑:
对于不离散化的状态, 需要哪些信息?
然后将这些信息离散化即可解决问题