csp7连测day7T2

离散化不难想到，关键是细节处理。
没有离散化的版本是这样的

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e5 + 10;
int cut[M], l[N], r[N];
int T, n, m, mx;

int main(void)
{
    scanf("%d", &T);
    for (int _ = 1; _ <= T; _++)
    {
        memset(cut, 0, sizeof cut);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", l + i, r + i);
            mx = max(mx, r[i]);
            for (int j = l[i] + 1; j < r[i]; j++)
                cut[j]++;
        }
        sort(cut + 1, cut + mx + 1, greater<int>());
        int ans = n;
        for (int i = 1; i <= m; i++)
            ans += cut[i];
        printf("Case #%d: %d\n", _, ans);
    }
}

他甚至没有加差分优化

于是我们只要开若干个数组，存这段位置可以砍断的区间个数个长度，排序后直接模拟。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10, M = 900000 + 10;
#define LL long long

int T, n;
LL m;

struct Data
{
	LL l, r;
	bool operator<(Data b)
	{
		return l != b.l ? l > b.l : r < b.r;
	}
	
} a[N], b[M];

int main()
{
	scanf("%d", &T);
	int pp = 0;
	while (T--)
	{
		scanf("%d%lld", &n, &m);
		map<LL, LL> ml, mr;
		for (int i = 1; i <= n; i++)
			scanf("%lld%lld", &a[i].l, &a[i].r),
				ml[a[i].l]++, ml[a[i].r] = ml[a[i].r], mr[a[i].r]++;// 这里ml[a[i].r] = ml[a[i].r] 的作用是如果ml[a[i].r]没有建立就建立并设为0，否则不变

		LL pre = 1, s = 0, len = 0;
		for (auto z : ml)
		{
			LL x = z.first, y = z.second;
			if (x - pre - 1 > 0)
				b[++len] = {s, x - pre - 1};
			s -= mr[x];
			b[++len] = {s, 1};
			s += ml[x];
			pre = x;
		}
		sort(b + 1, b + 1 + len);

		LL ans = 0;
		for (int i = 1; i <= len; i++)
		{
			if (b[i].r < m)
			{
				m -= b[i].r;
				ans += b[i].r * b[i].l;
			}
			else
			{
				ans += b[i].l * m;
				break;
			}
		}

		printf("Case #%d: %lld\n", ++pp, ans + n);
	}
	return 0;
}