ZROI-21-CSP7连-DAY 7 T2

Yorg / 2024-10-23 / 原文

题面

挂个 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;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

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 != MaxPos)
        {
            Cut[i].Len = Back[i + 1] - Back[i];
        }else{
            Cut[i].Len = 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()
{

    T = read();
    for (int Case = 1; Case <= T; Case++)
    {
        n = read();
        m = read();
        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
*/