YACS 2022年9月月赛 甲组 T2 区间交集（三） 题解

所以说，我又来贴标程了。

这题有很多做法，线段树，优先队列$and$删除等等，

这里分享一种码量极少的二分做法，主要思路：二分+动归

#include <bits/stdc++.h>
using namespace std;
int n, m, a[500005], cnt[2][500005];
long long num[2][500005];
int check(int x)
{
    num[0][1] = cnt[0][1] = 0;
    num[1][1] = a[1] + x, cnt[1][1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        num[0][i] = (num[0][i - 1] > num[1][i - 1] ? num[0][i - 1] : num[1][i - 1]);
        cnt[0][i] = (num[0][i - 1] > num[1][i - 1] || num[0][i - 1] == num[1][i - 1] && cnt[0][i - 1] < cnt[1][i - 1] ? cnt[0][i - 1] : cnt[1][i - 1]);
        num[1][i] = a[i] + (num[0][i - 1] + x > num[1][i - 1] ? num[0][i - 1] + x : num[1][i - 1]);
        cnt[1][i] = (num[0][i - 1] + x > num[1][i - 1] || num[0][i - 1] + x == num[1][i - 1] && cnt[0][i - 1] + 1 < cnt[1][i - 1] ? cnt[0][i - 1] + 1 : cnt[1][i - 1]);
    }
    return (num[0][n] > num[1][n] || (num[0][n] == num[1][n] && cnt[0][n] < cnt[1][n]) ? cnt[0][n] : cnt[1][n]);
}
int main()
{
    n = 1;
    while (cin >> a[n]) ++ n;
    n -= 2;
    m = a[n + 1];
    int l = -1e9, r = 1e9;
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        int x = check(mid);
        if (x <= m) l = mid;
        else r = mid;
    }
    if (l >= 0)
    {
        check(0);
        cout << max(num[0][n], num[1][n]) << endl;
    }
    else
    {
        check(l);
        cout << max(num[0][n], num[1][n]) - 1LL * m * l << endl;
    }
    return 0;
}